GATE 2026 CS (CS1) – Question 40
Let $P$ be the set of all integers from 1 to 15. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 5
Explanation
A complete binary tree with 15 nodes is a full, balanced binary tree of height 3.
Since an in-order traversal of any BST yields the sorted sequence $\{1, 2, \dots, 15\}$, the exact structure and keys of the nodes at each level of the unique complete BST of 15 keys are fixed:
- Root (level 0): 8
- Level 1: 4 (left child of 8), 12 (right child of 8)
- Level 2: 2, 6 (children of 4); 10, 14 (children of 12)
- Level 3: 1, 3, 5, 7, 9, 11, 13, 15
For a key to be placed into the BST without altering the tree shape, all of its ancestors in the tree must already be inserted before it.
- Ancestors of 4: $\{8\}$ (can be inserted 2nd or 3rd).
- Ancestors of 2: $\{8, 4\}$ (can be inserted 3rd, e.g. insertion order: 8, 4, 2).
- Ancestors of 10: $\{8, 12\}$ (can be inserted 3rd, e.g. insertion order: 8, 12, 10).
- Ancestors of 5: The path from the root to node 5 is $8 \to 4 \to 6 \to 5$. Thus, nodes 8, 4, and 6 must ALL be inserted into the tree before 5 can be inserted. Hence, at least 3 elements must precede 5, meaning 5 can be at earliest the 4th element inserted.
Therefore, 5 can NEVER be the third element inserted. Option (D) is correct.