GATE CS 2026 (Afternoon) — Question 49

Data StructuresBinary Search Trees (BSTs) & Binary HeapsMSQ2 marksHard

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 \( \text{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 \( \text{Suc}(V) \) denote the node that is its inorder successor. If a node \( V \) does not have an inorder successor, then \( \text{Suc}(V) \) is NULL. As there are no duplicates, if \( \text{Suc}(V) \) is not NULL, then \( \text{Val}(V) < \text{Val}(\text{Suc}(V)) \). Corresponding to every leaf node \( L_i \) that has a non-NULL \( \text{Suc}(L_i) \), a new key \( k_i \) with the following property is to be inserted into the BST. \( \text{Val}(L_i) < k_i < \text{Val}(\text{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?
  1. A
    \( K \) cannot have any duplicates
  2. B
    \( K \) will have at least one element
  3. C
    After inserting all keys from \( K \), the height of the BST can increase at most by one
  4. D
    Number of nodes in the BST will double after inserting all keys from \( K \)
Practise the full 2026-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Binary Search Trees (BSTs) & Binary HeapsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group