Question

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. 𝐾 cannot have any duplicates
• B. 𝐾 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 𝐾

Hint:

Recall that an inorder traversal lists BST keys in strictly increasing order, and Suc(V) is simply the next value in that list. Each new key fills a unique gap right after a leaf that has no right child, so it must attach as that leaf's right child - this controls both the no-duplicates property and the height-growth bound.

Answer 1

The Correct Option is A, C

Step 1: Setup. An inorder traversal of a BST visits nodes in strictly increasing order of key value. So if we list all node values in the tree by inorder traversal, we get a strictly increasing sequence \(v_1 < v_2 < \dots < v_m\) where \(m\) is the total number of nodes. For any node \(V\) that is not the last node in this sequence, \(Suc(V)\) is exactly the next value in this sequence.

Step 2: Check option A (no duplicates in K). For each leaf \(L_i\) with a non-NULL successor, we insert a key \(k_i\) with \(Val(L_i) < k_i < Val(Suc(L_i))\). Because the inorder sequence is strictly increasing and \(Suc(L_i)\) is the node immediately after \(L_i\) in this sequence, the open interval \((Val(L_i), Val(Suc(L_i)))\) contains no existing key of the tree. For two different leaves \(L_i\) and \(L_j\), their intervals are built from disjoint consecutive pairs of the same increasing sequence, so the intervals never overlap. A value chosen from one interval can never equal a value chosen from another disjoint interval, so \(K\) can never contain duplicates. Option A is TRUE.

Step 3: Check option B (K has at least one element). Consider the smallest possible BST: a single node tree with \(n = 1\) leaf. That one node has no inorder successor, so \(Suc(L_1) = NULL\) and no key is generated. Here \(K\) is empty for this valid tree. Option B is FALSE (a valid counterexample exists).

Step 4: Check option C (height increases by at most one). Since \(L_i\) is a leaf, it has no right child. When \(k_i\) is inserted using the standard BST-insert procedure, the search path reaches \(L_i\) because \(k_i\) is strictly greater than \(Val(L_i)\) and strictly less than every key that would redirect the search elsewhere, being squeezed exactly between \(L_i\) and its successor. Since \(L_i\) has no right child, \(k_i\) is attached as the right child of \(L_i\). So every new key becomes a child of an existing leaf, placed exactly one level below its parent leaf, and no branch grows by more than one node. Therefore the height of the tree can go up by at most \(1\). Option C is TRUE.

Step 5: Check option D (number of nodes doubles). \(K\) is generated only for leaves whose successor is non-NULL, i.e. all leaves except possibly the leaf holding the overall maximum key. So \(|K| \le (\text{number of leaves})\), while the tree also contains internal nodes. Total nodes after insertion is strictly less than double the original count whenever an internal node exists, and for the single-node tree \(|K| = 0\) so it certainly does not double. Option D is FALSE.

Conclusion: The true statements are A and C.

\[ \boxed{\text{Correct options: A and C}} \]