Binary Trees and Tree Algorithms

Question 1 Multiple Choice (Single Answer)

Which of the following statements is wrong about trees?

A binary tree is the one in which the internal nodes have atmost two children.
File system in unix OS make use of trees.
In a complete binary tree, the number of internal nodes is 1 less than the number of leaves.
In a binary tree, the number of internal nodes is greater than the number of leaves.
A tree with n nodes can have a maximum height n -1.

Question 2 Multiple Choice (Single Answer)

Which of the following is correct?

A. Running time cost O(n) B. Running time cost O(1) C. Running time cost O(logn)

A search operation in an ordered list will take C.
An insert operation in an ordered list will take B.
A search operation in an un ordered list will take B.
An insert operation in an un ordered list will take A.
1 and 2 are correct.

Question 3 Multiple Choice (Single Answer)

Given a traversal result abcdfge and following statements -

Above traversal is PreOrder Traversal
Above traversal is PostOrder Traversal
Above traversal is InOrder Traversal
For the given tree, a is the root of the tree
For the given tree, e is the root of the tree
Which of the above statements is/are correct?

Given an algorithm to traverse a tree Traverse(Node v){ visit(v); for each child w of v Traverse(w); }

1 and 5
2 and 5
3 and 4
2 and 4
1 and 4

Question 4 Multiple Choice (Single Answer)

What would come in place of y and z respectively in the above algorithm?

An iterative algorithm to search for key k in a tree T is given below-
search(T,k)
{
x = root(T);
while(x!=null or x!= k)
{
if(x < k) x= right[x];
else y
}
return z;
}

x = left[x] and x respectively
x = k and x respectively
x = right[x] and x respectively
x = left[right[x]] and k respectively
x != right[x] & x respectively

Question 5 Multiple Choice (Single Answer)

The above algorithm ____________.

Following is an algorithm to return a key in a BST(Binary Search Tree).
Returnkey(Tree T)
{
x= root[T];
while(right[x] != null)
{
x = right[x];
}
return x;
}

finds the maximum key in the tree
finds the minimum key in the tree
finds the root key in the tree
finds the rightmost leaf-key in the tree
finds the maximum internal node in the tree

Question 6 Multiple Choice (Single Answer)

After insertion of n keys, worst case running time of the algorithm would be _______________

An iterative algorithm to search for key k in a tree T is given below-
Assume that the tree has n nodes and height h.
search(T,k)
{
x = root(t);
while(x!=null or x!= k)
{
if(x > k) x= left[x];
else x = right[x];
}
return x;
}

O(h)
O(n)
O(nh)
O(n²)
O(h²)

Question 7 Multiple Choice (Single Answer)

This algorithm _______.

Given below is an algorithm:
if(right[x] != null)
{
x = right[x];
Treemin(x);
}
else
{
y = parent[x];
while(y !=null && x = right[y])
{
x=y; y=parent[y];
}
return y;
}

finds the successor of key x in the tree
finds the predecessor of key x in the tree
finds the maximum key in the tree
finds the minimum key in the tree
none of the above

Question 8 Multiple Choice (Single Answer)

Given numbers 1, 2, 3, 4, 5, 6…. N. Inorder to insert a random permutation of the numbers in binary search tree, what is the average running time?

O(logn)
O(nlogn)
O(n²)
O(n)
O(1)

Question 9 Multiple Choice (Single Answer)

What technique is used to get a good running time for an algorithm such as quick sort, which has bad worst case running time but good average case?

Randomization
Polymorphism
Synchronization
Inheritance
Encapsulation

Question 10 Multiple Choice (Single Answer)

Which of the following is not correct about quicksort algorithm?

The partition method returns the position of pivot element as it should be in the final sorted array.
The average running time of quicksort is O(nlogn).
Quicksort is faster than insertion sort and bubble sort.
Best case running time of quicksort is O(nlogn).
Worst case running time of quicksort is O(nlogn).

Question 11 Multiple Choice (Single Answer)

Which of the following statements is incorrect about a complete binary tree with n nodes and height h?

Level i has 2ⁱnodes.
Total number of internal nodes = Number of leaves - 1.
Total number of leaves is 2^h+1 - 1.
The relation between the height and number of nodes is h = log₂(n + 1/2).
Number of internal nodes is 2^h - 1.

Question 12 Multiple Choice (Single Answer)

What is the running time of the algorithm?

An iterative algorithm to search for key k in a tree T is given below. Assume that the tree has n nodes and height h.
search(T,k)
{
x = root(t);
while(x!=null or x!= k)
{
if(x < k) x= right[x];
else x = left[x];
}
return x;
}

O(n)
O(n²)
O(nh)
O(h)
O(h²)

Question 13 Multiple Choice (Single Answer)

What would come in place of two in the above algorithm?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T]; i
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
y = x;
x = left[x];
flag = 1;
}
else
{
y = x;
x = right[x];
flag = 2;
}
}
if(flag ==1)
{
k = ?;
}
else
{
k = ?;
}
}

right[x] and left[x] respectively
right[y] and left[y] respectively
left[x] and right[x] respectively
left[y] and right[y] respectively
left[x] and left[y] respectively

Question 14 Multiple Choice (Single Answer)

Given a sequence of numbers 8, 4, 9, 3, 2, 0, 11, 10 to be inserted in the tree. Which key will be visited last in the inorder traversal of the inserted keys?

Here is an algorithm to insert a key k in a binary search tree T.
insert(T,k)
{
int flag = 0;
node x = root[T];
if(x == null)
{
root = new node(k);
}
while(x != null)
{
if(x > k)
{
Y = x;
X = left[x];
flag = 1;
}
else
{
Y = x;
X = right[x];
flag = 2;
}
}
if(flag ==1)
{
K = left[y];
}
else
{
K = right[y];
}
}

10
9
11
8
4

Question 15 Multiple Choice (Single Answer)

What should come in place of ? in the above algorithm?

An algorithm to delete the node/key k from a tree T is given below:
delete(T, k)
{
if(left[k] == null && right[k] == null)
{
K = null;
}
else if(left[k] != null && right[k] == null)
{
if(k == left[parent[k]]) left[parent[k]] == left[k];
else right[parent[k]] = left[k];
}
else if(left[k] == null && right[k] != null)
{
if(k == left[parent[k]]) left[parent[k]] == right[k];
else right[parent[k]] = right[k];
}
else Y = ?;
X = y;
Right[x] = left[y];
}
}

Treemax(T)
Successor(T, k)
Predecessor(T, k)
Treemin(T)
Root[T]

Binary Trees and Tree Algorithms

Questions