Exercise: Questions on Binary Search Trees


Questions on Binary Search Trees : Question 1 :
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?

O(n) for all
O(Logn) for all
O(Logn) for search and insert, and O(n) for delete
O(Logn) for search, and O(n) for insert and delete
Show Answer
Questions on Binary Search Trees : Question 2 :
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?

Inorder Successor is always a leaf node
Inorder successor is always either a leaf node or a node with empty left child
Inorder successor may be an ancestor of the node
Inorder successor is always either a leaf node or a node with empty right child
Show Answer
Questions on Binary Search Trees : Question 3 :
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? (GATE CS 2011)

0
1
n!
(1/(n+1)).2nCn
Show Answer
Questions on Binary Search Trees : Question 4 :
How many distinct binary search trees can be created out of 4 distinct keys?

4
14
24
42
Show Answer
Questions on Binary Search Trees : Question 5 :
Which of the following traversal outputs the data in sorted order in a BST?

Preorder
Inorder
Postorder
Level order
Show Answer
Questions on Binary Search Trees : Question 6 :
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

7 5 1 0 3 2 4 6 8 9
0 2 4 3 1 6 5 9 8 7
0 1 2 3 4 5 6 7 8 9
9 8 6 4 2 3 0 1 5 7
Show Answer
Questions on Binary Search Trees : Question 7 :
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)? (GATE CS 2004)

2
3
4
6
Show Answer
Questions on Binary Search Trees : Question 8 :
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

10, 20, 15, 23, 25, 35, 42, 39, 30
15, 10, 25, 23, 20, 42, 35, 39, 30
15, 20, 10, 23, 25, 42, 35, 39, 30
15, 10, 23, 25, 20, 35, 42, 39, 30
Show Answer
Questions on Binary Search Trees : Question 9 :
Consider the following Binary Search Tree

               10
             /    \
            5      20
           /      /  \           
          4     15    30
               /  
              11       
If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?

2.75
2.25
2.57
3.25
Show Answer
Questions on Binary Search Trees : Question 10 :
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder

Any one of the given three traversals is sufficient
Either 2 or 3 is sufficient
2 and 3
1 and 3
Show Answer