GATE CSE 2026 | Set 2 | Data Structures | Memory Based | Question 14

Consider a Binary Search Tree (BST) in which all keys are distinct. For a node $v_i$, let $\text{succ}(v_i)$ denote its in-order successor. If $v_i$ has no in-order successor, then $\text{succ}(v_i) = \text{NULL}$.

Define a set $K$ as follows:

For every leaf node $v_i$ such that $\text{succ}(v_i) \ne \text{NULL}$, choose a key $k_i$ satisfying
\[
\text{val}(v_i) < k_i < \text{val}(\text{succ}(v_i))
\]
and include $k_i$ in $K$. $($Assume such a key can be chosen whenever $\text{succ}(v_i) \ne \text{NULL})$.

Now, insert all keys of $K$ into the given BST (in any order), maintaining the BST property.

Which of the following statements is/are necessarily true?

1. $K$ contains no duplicate keys.
    
2. After inserting all keys from $K$, the height of the BST increases by at most $1$.
    
3. After inserting all keys from $K$, the number of nodes in the BST becomes exactly double.
    
4. The set $K$ is non-empty (contains at least one key).