GATE 2026 CS (CS1) – Question 23
Let $n$ be an odd number greater than 100. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1. Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $\frac{n-1}{2}$; (C) $\frac{n-3}{2}$
Explanation
In a 1-indexed binary heap with $n$ elements:
- The children of node $i$ are at indices $2i$ and $2i + 1$.
- A node $i$ is an internal (non-leaf) node if it has at least one child, i.e., $2i \le n \iff i \le \lfloor n/2 \rfloor$.
- A node $i$ is a leaf node if $2i > n \iff i \ge \lfloor n/2 \rfloor + 1$.
Since $n$ is an odd number, $\lfloor n/2 \rfloor = \frac{n-1}{2}$.
- Leaf nodes occupy indices from $\frac{n-1}{2} + 1 = \frac{n+1}{2}$ up to $n$.
- Internal nodes occupy indices from $1$ to $\frac{n-1}{2}$.
Evaluating the options:
- (A) $\frac{n+1}{2}$ is the very first leaf node.
- (B) $\frac{n-1}{2}$ is the last internal node, so it is NOT a leaf node.
- (C) $\frac{n-3}{2}$ is an internal node, so it is NOT a leaf node.
- (D) $n$ is the last leaf node.
Therefore, indices that do NOT correspond to any leaf node are (B) and (C).