Which of the following indices of P do/does NOT correspond to any leaf node of the minheap?
Correct : b,c
In a binary heap stored in a 1-indexed array of n elements, node at index i is a leaf if and only if its left child index 2i exceeds n, i.e., i > n/2. Since n is odd, ⌊n/2⌋ = (n−1)/2. So all leaves are at indices from (n+1)/2 to n, and all internal nodes (non-leaves) are at indices 1 to (n−1)/2.
Option A — (n+1)/2 — IS a leaf
Since n is odd, (n+1)/2 is a whole number. This is exactly the first leaf node in the heap. Its left child would be at index n+1 which exceeds n, confirming it is a leaf. A is not the answer.
Option B — (n−1)/2 — NOT a leaf (internal node)
(n−1)/2 is strictly less than (n+1)/2, so it falls in the internal node range. Its left child is at index 2 × (n−1)/2 = n−1 ≤ n, meaning it has at least one child. So it is an internal node, not a leaf. B is correct.
Option C — (n−3)/2 — NOT a leaf (internal node)
(n−3)/2 = (n−1)/2 − 1, which is even further into the internal node region. Its left child is at n−3+2 = n−1 ≤ n, confirming it has children. C is also an internal node and correct.
Option D — n — IS a leaf
The last element n always has no children since its left child would be at 2n which is far beyond the array. It is definitely a leaf. D is not the answer.
Correct answer: B and C ✓
Similar Questions
Total Unique Visitors