GATE 2026 CS2 Q.49: solution and answer

GATE 2026 · CS2Q.49 · 2 marks · MSQ

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 $V a l (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 $S u c (V)$ denote the node that is its inorder successor. If a node $V$ does not have an inorder successor, then $S u c (V)$ is $N U LL$ . As there are no duplicates, if $S u c (V)$ is not $N U LL$ , then $V a l (V) < V a l (S u c (V))$ .

Corresponding to every leaf node $L_{i}$ that has a non-NULL $S u c (L_{i})$ , a new key $k_{i}$ with the following property is to be inserted into the BST.

V a l (L_{i}) < k_{i} < V a l (S u c (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?

(A)
$K$ cannot have any duplicates
(B)
$K$ will have at least one element
(C)
After inserting all keys from $K$ , 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 $K$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The true statements are (A) K cannot have any duplicates, and (C) the height of the BST can increase by at most one after inserting all keys from K.

Official answer: A, CSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Key fact: Suc(V) is defined with respect to the inorder traversal of the WHOLE tree, i.e. the full sorted sequence of all n' node values (not just leaves). So for any leaf L_i with Suc(L_i) ≠ NULL, the pair (Val(L_i), Val(Suc(L_i))) is a pair of values that are consecutive/adjacent in the tree's overall sorted order.
Since the values are distinct reals, the open interval (Val(L_i), Val(Suc(L_i))) between two values that are adjacent in sorted order contains no existing key, and any such 'gap' intervals for different leaves are pairwise disjoint (they are the gaps between different consecutive pairs of one fixed sorted sequence, and the successor map is injective — each node is the immediate successor of at most one node).
Hence whichever value k_i a leaf L_i contributes must lie strictly inside its own disjoint interval, so no two chosen keys k_i, k_j (i ≠ j) can be equal. Statement (A) — K cannot have duplicates — is TRUE.
Check (B): take n = 1 (a single node, which is simultaneously the root and the only leaf). This node holds the maximum (and only) key, so it has no inorder successor, Suc = NULL, and no key qualifies for insertion, so K = ∅. Statement (B) — K will have at least one element — is FALSE in general.
Check (C): L_i is a leaf, so it has no right child. For a value strictly between a node's value and its inorder successor's value with nothing in between, the standard BST-insertion rule is: it becomes the right child of the predecessor if the predecessor has no right child (which always holds here since L_i is a leaf), otherwise the left child of the successor. Since L_i always satisfies 'no right child', k_i is always inserted as the right child of L_i, i.e. at depth(L_i) + 1.
Because each k_i attaches only below its own leaf L_i (a leaf cannot be an ancestor of any other original node), inserting the keys for other leaves does not change L_i's depth or the search path down to it, so this holds regardless of insertion order. Since every leaf's depth is at most the tree's height h, every new node lands at depth ≤ h + 1, so the height after all insertions can increase by at most one. Statement (C) is TRUE.
Check (D): |K| = (number of leaves) − (1 if the global maximum node is itself a leaf, else 0), and the new total node count is (original nodes) + |K|. For a full/complete binary tree with n leaves, total original nodes = 2n − 1 and |K| = n − 1, giving a new total of 3n − 2, which is far less than doubling (2(2n − 1) = 4n − 2) for n > 0. Statement (D) — nodes will double — is FALSE in general.
So the true statements are (A) and (C).

KEY IDEA

Every leaf with a non-NULL successor sits at the boundary of a unique, pairwise-disjoint 'gap' in the tree's overall sorted key sequence, and — because a leaf has no right child — the new key for that gap is always forced to attach as that leaf's right child at depth exactly one more than the leaf's own depth.

WATCH OUT FOR

Treating Suc(V) as the inorder successor within the leaf sequence only (rather than the successor in the full tree's inorder traversal), or assuming the new key could land anywhere in the tree rather than realizing the 'no right child ⇒ becomes right child of the predecessor' insertion rule forces it to attach directly below its own leaf — both of which make it easy to wrongly reject (A) or (C), or to wrongly accept (B)/(D) without checking the n = 1 / full-tree counterexamples.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2026 CS2 Q.49: solution and answer

Answer and solution

More Trees & heaps questions