Question:hard
Consider a binary search tree (BST) with \(n\) leaf nodes (\(n>0\)). Given any node \(V\), the key present in the node is denoted as \(Val(V)\). All the keys present in the given BST are distinct. The keys belong to the set of real numbers.
For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).
Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST.
\[
Val(L_i) < k_i < Val(Suc(L_i))
\]
Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
Consider a binary search tree (BST) with \(n\) leaf nodes (\(n>0\)). Given any node \(V\), the key present in the node is denoted as \(Val(V)\). All the keys present in the given BST are distinct. The keys belong to the set of real numbers.
For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).
Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST. \[ Val(L_i) < k_i < Val(Suc(L_i)) \] Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).
Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST. \[ Val(L_i) < k_i < Val(Suc(L_i)) \] Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?
Show Hint
Since a leaf with a successor has no right child, the new key always becomes that leaf's new right child, going one level deeper than the leaf itself.
Updated On: Jul 22, 2026
- \(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\)
Show Solution
The Correct Option is A, C
Solution and Explanation
Step 1: Picture a small example first.
Take a BST with root $20$, left leaf $10$, and right leaf $30$. Here $Suc(10)=20$, which is not a leaf so it is not our concern, and $Suc(30)=NULL$ since $30$ is the maximum key in the tree. So among the leaves $10$ and $30$, only leaf $10$ gets a new key, some $k$ with $10<k<20$.
Step 2: Generalize the pattern for duplicates, this checks (A).
List every leaf that has a successor, in increasing order of key. The open gaps between each leaf and its successor never overlap, because each gap sits strictly between two consecutive values of the full sorted key list of the tree, and consecutive gaps in a sorted list never share a point. So each new key is pulled from its own private gap, and the whole list $K$ is automatically duplicate free. This confirms (A).
Step 3: Find a counterexample for at least one element, this checks (B).
A tree with just one node has that single node as both the first and last item in sorted order, so it has no successor at all. Then $K$ is the empty list, which directly disproves (B).
Step 4: Track exactly where insertion lands, needed for (C) and (D).
A leaf $L_i$ with a successor has no right child. The classic BST fact is that when a key has no right subtree, its successor is found by walking up until the first left turn, and this also means there is no key lying strictly between $L_i$ and $Suc(L_i)$ anywhere in the tree. Inserting a new key from this exact open gap therefore has to follow the path to $L_i$ and then drop in as the new right child of $L_i$, since $L_i$ has room on its right.
Step 5: Bound the height change, this checks (C).
Every insertion only ever adds a node one level below some existing leaf, and different insertions target different original leaves, so they cannot pile up on the same path. The tallest possible new leaf is therefore one level below whichever original leaf was tallest, so the height grows by at most $1$. This proves (C).
Step 6: Rule out doubling, this checks (D).
At most $n-1$ new nodes get added, all leaves except the single overall maximum key, while the tree could have far more than $n$ nodes in total once internal nodes are counted, so doubling is not guaranteed in general. (D) fails.
Step 7: Conclude.
\[ \boxed{\text{K has no duplicates, and the height rises by at most one, so (A) and (C) hold}} \]
Take a BST with root $20$, left leaf $10$, and right leaf $30$. Here $Suc(10)=20$, which is not a leaf so it is not our concern, and $Suc(30)=NULL$ since $30$ is the maximum key in the tree. So among the leaves $10$ and $30$, only leaf $10$ gets a new key, some $k$ with $10<k<20$.
Step 2: Generalize the pattern for duplicates, this checks (A).
List every leaf that has a successor, in increasing order of key. The open gaps between each leaf and its successor never overlap, because each gap sits strictly between two consecutive values of the full sorted key list of the tree, and consecutive gaps in a sorted list never share a point. So each new key is pulled from its own private gap, and the whole list $K$ is automatically duplicate free. This confirms (A).
Step 3: Find a counterexample for at least one element, this checks (B).
A tree with just one node has that single node as both the first and last item in sorted order, so it has no successor at all. Then $K$ is the empty list, which directly disproves (B).
Step 4: Track exactly where insertion lands, needed for (C) and (D).
A leaf $L_i$ with a successor has no right child. The classic BST fact is that when a key has no right subtree, its successor is found by walking up until the first left turn, and this also means there is no key lying strictly between $L_i$ and $Suc(L_i)$ anywhere in the tree. Inserting a new key from this exact open gap therefore has to follow the path to $L_i$ and then drop in as the new right child of $L_i$, since $L_i$ has room on its right.
Step 5: Bound the height change, this checks (C).
Every insertion only ever adds a node one level below some existing leaf, and different insertions target different original leaves, so they cannot pile up on the same path. The tallest possible new leaf is therefore one level below whichever original leaf was tallest, so the height grows by at most $1$. This proves (C).
Step 6: Rule out doubling, this checks (D).
At most $n-1$ new nodes get added, all leaves except the single overall maximum key, while the tree could have far more than $n$ nodes in total once internal nodes are counted, so doubling is not guaranteed in general. (D) fails.
Step 7: Conclude.
\[ \boxed{\text{K has no duplicates, and the height rises by at most one, so (A) and (C) hold}} \]
Was this answer helpful?
0
Top Questions on Binary Search Trees - Insertion Order and Tree Shape
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems