UPPCL AE 2018:65

Question

Consider that $\text{N}$ distinct elements $(\text{N}>3)$ are inserted into an initially empty binary search tree $\text{(BST)}.$ Which of the following statements are true?

• A. None of the above
• B. The worst case height of the resulting $\text{BST}$ is $\log_{2}\text{N}$
• C. Consider that a given order of insertion results in a $\text{BST}$ of height $ \text{N}.$ One can always find two elements in the original order where swapping the order of insertion of the two elements can half the height of the resulting $\text{BST}.$
• D. Swapping the order of insertion of any two elements can always half the height of the resulting $\text{BST}.$

Answer 1

Same is explained in testBook testSeries :

Concept:

Binary search tree:

A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

Option B: The worst-case height of the resulting BST is log2N.

False, If there are n nodes in a binary search tree, the maximum height of the binary search tree is n-1 and the minimum height is ceil(log2n). If the binary search tree has height n, a minimum number of nodes is n+1 (in the case of left-skewed and right-skewed binary search trees). So worst-case height of the resulting binary search tree is O(n).

Option D: Swapping the order of insertion of any two elements can always be half the height of the resulting BST.

False, Swapping the order of insertion of any two elements will not be always half the height of the resulting BST.

Option C: Consider that a given order of insertion results in a BST of height N. One can always find two elements in the original where swapping the order of insertion of the two elements can half the height of the resulting BST.

True,

Hence the correct answer is C : Consider that a given order of insertion results in a BST of height N. One can always find two elements in the original where swapping the order of insertion of the two elements can half the height of the resulting BST.

Comments

One can refer this explanation :

Option c is quite unique , need to make some graph for correctness .

An example is shown above.