Consider a binary search tree (BST) with π leaf nodes (π > 0). Given anyβ¦
2026
Consider a binary search tree (BST) with π leaf nodes (π > 0). Given any node π, the key present in the node is denoted as πππ(π). All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node π, let ππ’π(π) denote the node that is its inorder successor. If a node π does not have an inorder successor, then ππ’π(π) is πππΏπΏ. As there are no duplicates, if ππ’π(π) is not πππΏπΏ, then πππ(π) < πππ(ππ’π(π)).
Corresponding to every leaf node πΏπ that has a non-NULL ππ’π(πΏπ), a new key ππ with the following property is to be inserted into the BST.
πππ(πΏπ) < ππ < πππ(ππ’π(πΏπ))
Let πΎ represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
- A.
K cannot have any duplicates
- B.
K will have at least one element
- C.
After inserting all keys from πΎ, the height of the BST can increase at most by one
- D.
Number of nodes in the BST will double after inserting all keys from K
Attempted by 19 students.
Show answer & explanation
Correct answer: A, C
Core Idea
For every leaf LiL_iLiβ with successor:
Val(Li)<ki<Val(Suc(Li))\text{Val}(L_i) < k_i < \text{Val}(Suc(L_i))Val(Liβ)<kiβ<Val(Suc(Liβ))
So each new key lies strictly between two consecutive inorder elements
Option A: K cannot have duplicates
TRUE
Each kik_ikiβ lies in a unique open interval between two consecutive keys
Intervals do not overlap
So no two kik_ikiβ can be equal
Option B: K will have at least one element
FALSE
If BST has only one node (also a leaf)
It has no successor
No kik_ikiβ generatedOption C: Height increases at most by one
TRUE
Each kik_ikiβ is inserted between a leaf and its successor
So it becomes child of that leaf
Only extends leaf depth by 1
Option D: Number of nodes doubles
FALSE
New keys = number of leaves with successor
In skewed tree β only 1 such leaf
Not doubling
Final Answer:
A and C