Computer Sciences > GATE 2026 SET-1 > Heap
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
(n + 1) / 2
B
(n − 1) / 2
C
(n − 3) / 2
D
n

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

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ
Choose the word that is opposite in meaning to the word “coherent”.
#5 MCQ

Related Topics

binary min heap leaf nodes GATE 2026 GATE CS 2026 Set-1 Q36 heap leaf internal node index GATE n odd minheap non-leaf indices data structures heap GATE 2026 heap array 1-indexed leaf node GATE internal node index heap GATE

Unique Visitor Count

Total Unique Visitors

Loading......