Tutorial on Advanced Data structure and algorithms
Exercise1 : Below is a Binary tree
1. What is the height of node 6?
2. What is the height of node 3?
3. What is the depth of node 6?
4. What is the depth of node 3?
5. What is the degree of nodes 18, 6, 9 and 7 ?
6. What is the pre-order traversal of the tree?
7. What is the in-order traversal of the tree?
8. What is the post-order traversal of the tree?
Exercise2. Binary search tree.
1. Show the final BST after inserting 11, 9, 8, 2, 10, 5, 1, 4, 6, 7, 0, 3 into an empty BST.
2. What is the pre-order traversal of the tree?
3. What is the in-order traversal of the tree?
4. What is the post-order traversal of the tree?
5. What is the degree of nodes : 8,7,0 ?
Exercise 3 :
(a) Insert items with the following keys (in the given order) into an initially empty binary
search tree: 30, 40, 24, 58, 48, 26, 11, 13. Draw the tree after any two insertions.
Exercise 4:
For each of the algorithms PreorderTreeWalk, InorderTreeWalk, and PostorderTreeWalk
answer the following questions:
(a) Does the algorithm print the keys of elements stored in a binary search tree in a sorted
order? Why or why not?
Page 1 sur 6
Tutorial on Advanced Data structure and algorithms
Exercise 5 : Give the preorder, inorder, postorder,
and level-order
order traversals of the following binary trees.
Exercise 6
(a) Write a function that counts the number of items in a binary tree.
(b) Write a function that returns the sum of all the keys in a binary tree.
(c) Write a function that returns the maximum value of all the keys in a binary
tree. Assume all values are nonnegative; return -1
1 if the tree is empty.
Exercise 7 :
Write a C function that prints all the keys less than a given value v in a binary tree.
Page 2 sur 6
Tutorial on Advanced Data structure and algorithms
Exercise 8
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
int a = 0;
for (i = 0; i < N; i++) {
for (j = N; j > i; j--) {
a = a + i + j;
}
}
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
}
int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}
Explanation: We have to find the smallest x such that ‘(N / 2^x )< 1 OR 2^x > N’
var value = 0;
for(var i=0;i<n;i++)
for(var j=0;j<i;j++)
value += 1;
Exercise 9
What is the (asymptotic) running time of each of the following algorithms, as a function of n?
Justify your answers.
Page 3 sur 6
Tutorial on Advanced Data structure and algorithms
To)
for i = 1 to n do
for j = 1 to 2n + 1 do
print ("Hello World)
end for
end for
b)
for i = 1 to 10 do
for j = 1 to n do
print ("Hello World")
end for
end for
vs)
for i = 1 to n do
for j = i to n do
print ("Hello World")
end for
end for
d)
for i = 1 to n do
for j = 1 to 2 ∗ i + 1 do
print ("Hello World")
Page 4 sur 6
Tutorial on Advanced Data structure and algorithms
end for
end for
e)
for i = 1 to n ∗ n do
for j = 1 to i do
print ("Hello World")
end for
end for
f)
for (i = 0 to m) do
t←1
while (t <m) do
print ("Hello world")
t←t∗2
end while
end for
Exercise 10
What is the worst-case complexity of the each of the following code fragments?
Two loops in a row:
1. for (i = 0; i <N; i ++) {
2. sequence of statements}
Page 5 sur 6
Tutorial on Advanced Data structure and algorithms
3. for (j = 0; j <M; j ++) {
4. sequence of statements}
How would the complexity change if the second loop went to N instead of M?
A nested loop followed by a non-nested loop:
7. for (i = 0; i <N; i ++) {
8. for (j = 0; j <N; j ++) {
9. sequence of statements
10. }}
11. for (k = 0; k <N; k ++) {
12. sequence of statements}
A nested loop in which the number of times the inner loop executes depends on the value of
the outer loop index:
13. for (i = 0; i <N; i ++) {
14. for (j = N; j> i; j–) {
15. sequence of statements
16. }}
Page 6 sur 6
