Consider a binary search tree (BST) with n leaf nodes (n 0). All keys are distinct real numbers. F

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2026 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2026 question covers Binary Search Trees (BST) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2026 Data Structures question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider a binary search tree (BST) with n leaf nodes (n > 0). All keys are distinct real numbers. For a node V, Suc(V) denotes its inorder successor (NULL if none). Corresponding to every leaf node L_i that has a non-NULL Suc(L_i), a new key k_i with Val(L_i)

Accepted Answer

Correct Answer: (A) and (C)Concept -- BST Insertion Analysis: • A (TRUE): Each k_i lies strictly between Val(L_i) and Val(Suc(L_i)). Since the intervals (Val(L_i), Val(Suc(L_i))) for different leaves are disjoint (because inorder traversal gives sorted order), no two k_i can be equal. So K has no duplicates.• B (FALSE): If the BST has only one leaf (i.e., a single node tree), then that leaf has no successor, so K is empty. Thus K may have zero elements.• C (TRUE): Each new key is inserted as a direct child of either L_i or Suc(L_i). It adds exactly one level below an existing leaf, increasing the height by at most 1 (since the deepest leaf may become one level deeper).• D (FALSE): The number of new keys is at most n-1 (one for each adjacent pair of leaves in inorder). The original BST has at most 2n-1 nodes. After insertion, total nodes ≤ 2n-1 + (n-1) = 3n-2, which is less than double (2*(2n-1)=4n-2 for n>1). So nodes do not double.Note: Inserting keys between existing keys in a BST increases the tree’s size but not necessarily the height dramatically if inserted at leaves.

Consider a binary search tree (BST) with n leaf nodes (n > 0). All keys are distinct real numbers. For a node V, Suc(V) denotes its inorder successor (NULL if none). Corresponding to every leaf node L_i that has a non-NULL Suc(L_i), a new key k_i with Val(L_i)

Master GATE-CS with Our Test Series

More Questions from Binary Search Trees (BST)

Frequently Asked Questions

Consider a binary search tree (BST) with n leaf nodes (n > 0). All keys are distinct real numbers. For a node V, Suc(V) denotes its inorder successor (NULL if none). Corresponding to every leaf node L_i that has a non-NULL Suc(L_i), a new key k_i with Val(L_i)

Master GATE-CS with Our Test Series

More Questions from Binary Search Trees (BST)

Frequently Asked Questions