GATE CS 2026 Set 2 Q39 — Searching, Sorting, Hashing

Let the sorted order of all keys in the BST be $x_1 < x_2 < \dots < x_m$.

• Statement A is TRUE: Each leaf node $L_i$ corresponds to some unique element $x_p$ in the sorted sequence. Its inorder successor $\operatorname{Suc}(L_i)$ is the next element $x_{p+1}$. The key $k_i$ is chosen from the open interval $(x_p, x_{p+1})$. Since all leaf nodes are distinct, their corresponding indices $p$ are distinct. The open intervals $(x_p, x_{p+1})$ for distinct $p$ are mutually disjoint, meaning no two keys in $K$ can be equal. Thus, $K$ cannot have any duplicates.
• Statement B is FALSE: If the BST consists of a single node (which is a leaf), its inorder successor is $\text{NULL}$. In this case, $K$ is empty and has $0$ elements.
• Statement C is TRUE: For any leaf $L_i$, the key $k_i$ lies strictly between $\operatorname{Val}(L_i)$ and $\operatorname{Val}(\operatorname{Suc}(L_i))$. During BST insertion, the search path for $k_i$ will follow the exact same path as $L_i$. Upon reaching $L_i$, since $k_i > \operatorname{Val}(L_i)$, it will be inserted as the right child of $L_i$. Since each leaf $L_i$ gets at most one child at depth $\operatorname{depth}(L_i) + 1$, the maximum depth (height) of the tree can increase by at most $1$.
• Statement D is FALSE: Consider a BST with root $2$, left child $1$, and right child $3$. The leaves are $1$ and $3$. Only leaf $1$ has a non-NULL successor ($2$). Thus, only one key is inserted, increasing the total number of nodes from $3$ to $4$, which is not double.