GATE CS 2026 Set 1 Q30 — Searching, Sorting, Hashing

A complete binary tree with $15$ nodes is a perfect binary tree of height $3$. Since it is a Binary Search Tree (BST) containing the keys $1$ to $15$, its structure is uniquely determined by the sorted order of the keys:

• Level 0 (Root): $8$
• Level 1: $4$ (left child of $8$), $12$ (right child of $8$)
• Level 2:
  • Children of $4$: $2$ and $6$
  • Children of $12$: $10$ and $14$
• Level 3 (Leaves):
  • Children of $2$: $1$ and $3$
  • Children of $6$: $5$ and $7$
  • Children of $10$: $9$ and $11$
  • Children of $14$: $13$ and $15$

For any element to be inserted into the BST, all of its ancestors must be inserted before it. Let's analyze the options:

• To insert $4$: Ancestor is $8$. Insertion sequence can be: $8 \to 12 \to 4$ (where $4$ is $3^{\text{rd}}$).
• To insert $2$: Ancestors are $8$ and $4$. Insertion sequence can be: $8 \to 4 \to 2$ (where $2$ is $3^{\text{rd}}$).
• To insert $10$: Ancestors are $8$ and $12$. Insertion sequence can be: $8 \to 12 \to 10$ (where $10$ is $3^{\text{rd}}$).
• To insert $5$: Ancestors are $8$, $4$, and $6$. All three of these must be inserted before $5$. Thus, $5$ can be inserted at earliest as the $4^{\text{th}}$ element.

Therefore, $5$ can never be the third element inserted.