Question 1 |

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

\Theta(n\log n) | |

\Theta(n) | |

\Theta(\log n) | |

\Theta(1) |

Question 1 Explanation:

Question 2 |

What is the in-order successor of 15 in the given binary search tree?

18 | |

6 | |

17 | |

20 |

Question 2 Explanation:

Question 3 |

The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19. Which one of the following is the postorder traversal of the tree?

10,11,12,15,16,18,19,20 | |

11,12,10,16,19,18,20,15 | |

20,19,18,16,15,12,11,10 | |

19,16,18,20,11,12,10,15 |

Question 3 Explanation:

Question 4 |

The pre-order transversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19,
17, 20. Then the post-order traversal of this tree is:

2,6,7,8,9,10,12,15,16,17,19,20 | |

2,7,6,10,9,8,15,17,20,19,16,12 | |

7,2,6,8,9,10,20,17,19,15,16,12 | |

7,6,2,10,9,8,15,16,17,20,19,12 |

Question 4 Explanation:

Question 5 |

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are :

Note: The height of a tree with a single node is 0.

Note: The height of a tree with a single node is 0.

4 and 15 respectively | |

3 and 14 respectively | |

4 and 14 respectively | |

3 and 15 respectively |

Question 5 Explanation:

Question 6 |

The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____.

Note: The height of a tree with a single node is 0.

Note: The height of a tree with a single node is 0.

2 | |

8 | |

64 | |

32 |

Question 6 Explanation:

Question 7 |

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

65 | |

67 | |

69 | |

83 |

Question 7 Explanation:

Question 8 |

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

\Theta (logn) for both insertion and deletion | |

\Theta (n) for both insertion and deletion | |

\Theta (n)for insertion and \Theta (logn) for deletion | |

\Theta (logn) for insertion and \Theta (n) for deletion |

Question 8 Explanation:

Question 9 |

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25

II. 5, 8, 9, 12, 10, 15, 25

III. 2, 7, 10, 8, 14, 16, 20

IV. 4, 6, 7, 9 18, 20, 25

I. 3, 5, 7, 8, 15, 19, 25

II. 5, 8, 9, 12, 10, 15, 25

III. 2, 7, 10, 8, 14, 16, 20

IV. 4, 6, 7, 9 18, 20, 25

I and IV only | |

II and III only | |

II and IV only | |

II only |

Question 9 Explanation:

Question 10 |

Consider the following binary search tree T given below: Which node contains the fourth smallest element in T?

Q | |

V | |

W | |

X |

Question 10 Explanation:

There are 10 questions to complete.