Let n be an odd number greater than 100. Consider a binary minheap with n elements stored in an arra

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2026 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2026 question covers Binary Heaps topic.

Q: What is the difficulty level of this question?

This GATE-CS 2026 Data Structures question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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

Accepted Answer

Correct Answer: (B) and (C)Concept -- Heap Structure and Leaf Node Identification: In a 1‑indexed binary heap with n elements, a node at index i is a leaf iff it has no children, i.e., 2i > n. This condition is equivalent to i > floor(n/2). Since n is odd, n/2 = (n−1)/2 (integer division). Therefore, leaves occupy indices floor(n/2)+1 through n. For odd n, floor(n/2) = (n−1)/2, so leaves start at (n−1)/2 + 1 = (n+1)/2. Thus indices from (n+1)/2 to n are leaves. Non‑leaf (internal) nodes are indices 1 through (n−1)/2. Check each option: A: (n+1)/2 ≥ (n+1)/2 — this is the first leaf index → leaf. B: (n−1)/2 = floor(n/2) — this is the last internal node → NOT a leaf. C: (n−3)/2 = floor(n/2)−1 — internal node → NOT a leaf. D: n — the last element, always a leaf. Hence B and C are not leaves. This property holds for any complete binary tree (heap) stored in an array.

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

Master GATE-CS with Our Test Series

More Questions from Binary Heaps

Frequently Asked Questions

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

Master GATE-CS with Our Test Series

More Questions from Binary Heaps

Frequently Asked Questions