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

Think of this problem in terms of the sorted list of key values obtained from an inorder scan of the BST, and what a 'gap-filling' insertion does to the shape of the tree.

Sorted view: Inorder traversal always outputs BST keys as a strictly increasing sequence \(v_1 < v_2 < \dots < v_m\). Every leaf \(L_i\) that is not the node holding the maximum key sits at some position in this list, and \(Suc(L_i)\) is simply the very next value in the list.

Testing 'no duplicates' (A): Each inserted key \(k_i\) is squeezed strictly between two consecutive values of this sorted list, i.e. it fills a specific unique gap. Two different leaves correspond to two different gaps in this same sorted list, since the list has no repeated values and each leaf contributes at most one gap right after it. Filling different gaps can never produce equal values, so duplicates in \(K\) are impossible. This makes A correct.

Testing 'K nonempty' (B) with a small example: Take a BST that is just a single node, say key = 5. It is the only leaf and also holds the maximum key, so it has no successor, meaning nothing gets added to \(K\). So \(K\) can be empty, hence B is incorrect.

Testing 'height grows by at most 1' (C): Take any leaf \(L_i\) whose successor exists. A leaf has an empty right subtree by definition. The value \(k_i\) is larger than \(Val(L_i)\) but smaller than everything that comes after \(Suc(L_i)\), so a normal BST insertion walks down to exactly \(L_i\) and then steps right into an empty spot, so \(k_i\) becomes the right child of \(L_i\). This happens independently for every qualifying leaf: each old leaf gets at most one new child directly beneath it. No insertion path ever needs to go deeper than one step past an existing leaf, so the tree height increases by at most 1. C is correct.

Testing 'nodes double' (D): The number of new keys equals the number of leaves that have a successor, which is at most the number of leaves, while the tree usually also has internal nodes that are not leaves. So the added node count is generally smaller than the original node count, and in the single-node example it is even zero. D is incorrect.

Final selected options: A and C.