Question:
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
Verified By Collegedunia
The Correct Option is A, C
Solution and Explanation
Step 1: Understand what \(K\) actually is.
Take the sorted, inorder, list of all keys already in the BST. For each leaf \(L_i\) that is not the very last key in this sorted order, that is, its inorder successor exists, we invent one brand new value \(k_i\) that sits strictly between \(Val(L_i)\) and \(Val(Suc(L_i))\), and nothing else in the tree lies in that open interval, since \(Suc(L_i)\) is by definition the next larger key already present.
Step 2: Check option (A), can \(K\) have duplicates?
Different leaves give different, non overlapping intervals. Since \(L_i\) and \(Suc(L_i)\) are consecutive values in the sorted order of the whole tree, the interval between them used for one leaf never overlaps the interval used for another leaf, because consecutive gaps in a sorted list never share a point. So the new keys chosen for different leaves are always forced into disjoint ranges, and no two of them can be equal. Statement (A) is true.
Step 3: Check option (B), does \(K\) always have at least one element?
Consider the smallest possible tree, a single node that is both the root and the only leaf (\(n=1\)). This single leaf is also the very last node in the inorder traversal, so its inorder successor is \(NULL\), and no new key gets created for it at all. Here \(K\) is empty, so it is false to claim \(K\) always has at least one element. Statement (B) is false.
Step 4: Work out where each new key gets inserted.
Take any leaf \(L_i\) with a non NULL successor. Because \(L_i\) is a leaf, it has no right child. In a BST, when a node has no right child, its inorder successor is the lowest ancestor for which that node lies in the left subtree, and there is no key value strictly between \(Val(L_i)\) and \(Val(Suc(L_i))\) anywhere else in the tree. This means \(k_i\), being strictly between these two, has \(L_i\) as its immediate predecessor in the tree. Standard BST insertion for \(k_i\) therefore follows the exact same root to leaf path taken to reach \(L_i\), then, since \(k_i>Val(L_i)\) and \(L_i\) has no right child, \(k_i\) becomes the new right child of \(L_i\).
Step 5: Check option (C), the height increase.
Every such insertion just described adds one node directly below an existing leaf, extending the depth of that one root to leaf path by exactly one level, without disturbing any other path in the tree. These insertions happen at different original leaves, so they do not interfere with each other. If \(H\) is the height of the tree before any insertion, then after inserting all of \(K\), any newly added node sits at depth at most \(H+1\), since it is one level below a leaf that was already at depth at most \(H\). So the new height is at most \(H+1\), meaning the height can increase by at most one. Statement (C) is true.
Step 6: Check option (D), does the node count double?
Only the leaves that have a non NULL successor gain a new child, which is at most \(n-1\) new nodes if there are \(n\) leaves, since the single rightmost, maximum valued leaf never gets a new child, having no successor. The total node count before insertion also includes all internal nodes, not just leaves, so the new node count is the old total plus at most \(n-1\), which is not generally equal to twice the old total. Statement (D) is false.
Step 7: Final answer.
The true statements are that \(K\) cannot repeat a value, and the height rises by at most one.
\[ \boxed{\text{(A) and (C)}} \]
Take the sorted, inorder, list of all keys already in the BST. For each leaf \(L_i\) that is not the very last key in this sorted order, that is, its inorder successor exists, we invent one brand new value \(k_i\) that sits strictly between \(Val(L_i)\) and \(Val(Suc(L_i))\), and nothing else in the tree lies in that open interval, since \(Suc(L_i)\) is by definition the next larger key already present.
Step 2: Check option (A), can \(K\) have duplicates?
Different leaves give different, non overlapping intervals. Since \(L_i\) and \(Suc(L_i)\) are consecutive values in the sorted order of the whole tree, the interval between them used for one leaf never overlaps the interval used for another leaf, because consecutive gaps in a sorted list never share a point. So the new keys chosen for different leaves are always forced into disjoint ranges, and no two of them can be equal. Statement (A) is true.
Step 3: Check option (B), does \(K\) always have at least one element?
Consider the smallest possible tree, a single node that is both the root and the only leaf (\(n=1\)). This single leaf is also the very last node in the inorder traversal, so its inorder successor is \(NULL\), and no new key gets created for it at all. Here \(K\) is empty, so it is false to claim \(K\) always has at least one element. Statement (B) is false.
Step 4: Work out where each new key gets inserted.
Take any leaf \(L_i\) with a non NULL successor. Because \(L_i\) is a leaf, it has no right child. In a BST, when a node has no right child, its inorder successor is the lowest ancestor for which that node lies in the left subtree, and there is no key value strictly between \(Val(L_i)\) and \(Val(Suc(L_i))\) anywhere else in the tree. This means \(k_i\), being strictly between these two, has \(L_i\) as its immediate predecessor in the tree. Standard BST insertion for \(k_i\) therefore follows the exact same root to leaf path taken to reach \(L_i\), then, since \(k_i>Val(L_i)\) and \(L_i\) has no right child, \(k_i\) becomes the new right child of \(L_i\).
Step 5: Check option (C), the height increase.
Every such insertion just described adds one node directly below an existing leaf, extending the depth of that one root to leaf path by exactly one level, without disturbing any other path in the tree. These insertions happen at different original leaves, so they do not interfere with each other. If \(H\) is the height of the tree before any insertion, then after inserting all of \(K\), any newly added node sits at depth at most \(H+1\), since it is one level below a leaf that was already at depth at most \(H\). So the new height is at most \(H+1\), meaning the height can increase by at most one. Statement (C) is true.
Step 6: Check option (D), does the node count double?
Only the leaves that have a non NULL successor gain a new child, which is at most \(n-1\) new nodes if there are \(n\) leaves, since the single rightmost, maximum valued leaf never gets a new child, having no successor. The total node count before insertion also includes all internal nodes, not just leaves, so the new node count is the old total plus at most \(n-1\), which is not generally equal to twice the old total. Statement (D) is false.
Step 7: Final answer.
The true statements are that \(K\) cannot repeat a value, and the height rises by at most one.
\[ \boxed{\text{(A) and (C)}} \]
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Binary Search Trees - Insertion Order and Tree Shape Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions