Which statements are true about inserting keys between BST leaf nodes and their inorder successors in GATE CS 2026 Set-2 Q49?

The correct answers are A, B, and C. A is true because intervals (Val(Li), Val(Suc(Li))) for different leaves are always disjoint in a BST since the inorder sequence is strictly sorted, making duplicate keys impossible. B is true because any BST with more than one node has at least one leaf with a non-NULL inorder successor. C is true because each ki inserts as a direct right child of leaf Li, adding at most one level to the BST height.

Why can K not have duplicates in GATE CS 2026 Set-2 Q49?

In a BST, the inorder traversal produces a strictly sorted sequence. The interval (Val(Li), Val(Suc(Li))) for each leaf node is completely disjoint from every other leaf's interval because no two leaves share the same consecutive inorder pair. Since the intervals never overlap, two different ki values chosen from different intervals can never be equal, so K cannot have duplicates.

BST Leaf Inorder Successor Key Insertion | GATE CS 2026 Set-2 Q49

Q: Why is option D false in GATE CS 2026 Set-2 Q49?

Option D claims the number of nodes doubles after inserting all keys from K. But the rightmost leaf node has no inorder successor and contributes nothing to K. So the number of new nodes inserted is strictly less than n, and the total cannot reach 2n. Doubling is impossible.

Computer Sciences > GATE 2026 SET-2 > Data Structures

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.
V𝑎𝑙(𝐿𝑖)< 𝑘𝑖< 𝑉𝑎𝑙(𝑆𝑢𝑐(𝐿𝑖))
Let 𝐾 represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

K cannot have any duplicates

K will have at least one element

After inserting all keys from K, the height of the BST can increase at most by one

Number of nodes in the BST will double after inserting all keys from K

Correct : a,b,c

Each new key k_i satisfies Val(L_i) < k_i < Val(Suc(L_i)), inserted for every leaf that has a non-NULL inorder successor.
Option A — True
In a BST the inorder sequence is strictly sorted and all keys are distinct. The interval (Val(L_i), Val(Suc(L_i))) for each leaf is completely disjoint from every other leaf's interval — no two leaves share the same consecutive inorder pair. Since all intervals are non-overlapping, it is impossible for two different k_i values chosen from different intervals to be equal. K cannot have duplicates. A is true.
Option B — True
Any BST with more than one node always has at least one leaf that is not the rightmost node, meaning at least one leaf has a non-NULL inorder successor. So K always has at least one element. B is true.
Option C — True
Since k_i > Val(L_i) and L_i is a leaf with no right child, every new key inserts as a direct right child of L_i, exactly one level below an existing leaf. Height increases by at most 1. C is true.
Option D — False
The rightmost leaf has no inorder successor and contributes nothing to K. So new nodes inserted are strictly less than n, and total nodes cannot reach 2n. Doubling is impossible. D is false.
Correct answer: A, B, C

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev