GATE 2026 CS1 Q.23: solution and answer

GATE 2026 · CS1Q.23 · 1 mark · MSQ

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?

(A)
$\frac{n + 1}{2}$
(B)
$\frac{n - 1}{2}$
(C)
$\frac{n - 3}{2}$
(D)
$n$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The indices that do NOT correspond to any leaf node are (B) $\frac{n - 1}{2}$ and (C) $\frac{n - 3}{2}$ .

Official answer: B, CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Rule: in a 1-indexed array-stored binary heap of n nodes, node i has children at 2i and 2i+1. Node i is internal iff 2i <= n, i.e., i <= floor(n/2); node i is a leaf iff i > floor(n/2).
Since n is odd, floor(n/2) = (n-1)/2. So internal (non-leaf) indices run from 1 to (n-1)/2, and leaf indices run from (n-1)/2 + 1 = (n+1)/2 up to n.
Option (A) (n+1)/2 equals floor(n/2) + 1, the very first leaf index, so it IS a leaf: it is NOT one of the required answers.
Option (B) (n-1)/2 equals floor(n/2) exactly, the last internal node, so it is NOT a leaf: this IS one of the required answers.
Option (C) (n-3)/2 equals floor(n/2) - 1, strictly inside the internal range, so it is NOT a leaf: this IS one of the required answers.
Option (D) n is the last stored element; its would-be children 2n and 2n+1 both exceed n, so it has no children and IS a leaf: it is NOT one of the required answers.
Sanity check with n = 101: floor(101/2) = 50, so leaves are indices 51 through 101. (A) 51 is a leaf. (B) 50 is internal (not a leaf). (C) 49 is internal (not a leaf). (D) 101 is a leaf. This confirms that (B) and (C) are exactly the indices that do NOT correspond to a leaf node.

KEY IDEA

In a 1-indexed array representation of an $n$ -node binary heap, node $i$ is internal iff $1 \leq i \leq ⌊ \frac{n}{2} ⌋$ (its children $2 i, 2 i + 1$ still lie within $1.. n$ ), and node $i$ is a leaf iff $i > ⌊ \frac{n}{2} ⌋$ . For odd $n$ , $⌊ \frac{n}{2} ⌋ = \frac{n - 1}{2}$ , so the last internal index is $\frac{n - 1}{2}$ and the first leaf index is $\frac{n + 1}{2}$ .

WATCH OUT FOR

Confusing the leaf-boundary index (the first leaf) with the last internal node. Since $⌊ \frac{n}{2} ⌋$ is itself the LAST internal node (not a leaf), and $⌊ \frac{n}{2} ⌋ + 1$ is the FIRST leaf, it is easy to mislabel option (A), $\frac{n + 1}{2}$ , as non-leaf, or to mislabel (B), $\frac{n - 1}{2}$ , as a leaf, by an off-by-one slip in the floor computation.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2026 CS1 Q.23: solution and answer

Answer and solution

More Trees & heaps questions