GATE CSE 2026 Session 2 Q49: Inserting a key between each BST leaf and its inorder successor

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?