The GATE Grind

GATE 2026 CS (CS2) – Question 49

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple select

Consider a binary search tree (BST) with $n$ leaf nodes, where $n>0$. All keys are distinct real numbers. For a node $V$, let $Suc(V)$ denote its inorder successor; if no inorder successor exists, then $Suc(V)$ is $NULL$. For every leaf node $L_i$ that has a non-$NULL$ successor, a new key $k_i$ is chosen such that $Val(L_i) < k_i < Val(Suc(L_i))$. Let $K$ be the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

  1. $K$ cannot have any duplicates.
  2. $K$ will have at least one element.
  3. After inserting all keys from $K$, the height of the BST can increase at most by one.
  4. The number of nodes in the BST will double after inserting all keys from $K$.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $K$ cannot have any duplicates.; (C) After inserting all keys from $K$, the height of the BST can increase at most by one.

Explanation

For each eligible leaf $L_i$, the interval $(Val(L_i), Val(Suc(L_i)))$ is a distinct consecutive inorder gap in the BST. Hence two different leaves cannot generate the same new key interval, so $K$ cannot contain duplicates; thus (A) is true. Statement (B) is false because if the BST has only one node, that leaf has no inorder successor, so $K$ can be empty. Each new key inserted from such an interval becomes the right child of the corresponding leaf, so the height can increase by at most one; thus (C) is true. Statement (D) is false because at most one new node is added per eligible leaf, so the number of nodes need not double. Therefore, the correct choices are (A) and (C).