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

In a 1-indexed binary heap of size $n$, a node at index $i$ is a leaf node if and only if it has no children.

The left child of a node at index $i$ is located at index $2i$. Therefore, node $i$ is a leaf node if:

Since $n$ is given to be an odd number, we can write $n = 2k + 1$ for some integer $k$. Substituting this into the inequality:

Since $k = \frac{n-1}{2}$, the leaf nodes are located at indices:

Thus, the indices corresponding to leaf nodes are from $\frac{n+1}{2}$ to $n$. The indices corresponding to non-leaf (internal) nodes are from $1$ to $\frac{n-1}{2}$.

Let's evaluate each option:

• Option A: $\frac{n+1}{2}$ is the first leaf node.
• Option B: $\frac{n-1}{2}$ is the last non-leaf node. Hence, it is not a leaf node.
• Option C: $\frac{n-3}{2}$ is less than $\frac{n-1}{2}$, so it is a non-leaf node. Hence, it is not a leaf node.
• Option D: $n$ is the last element of the heap, which is a leaf node.

Therefore, the indices that do NOT correspond to any leaf node are B and C.