GATE 2025 CS1 Q.35: solution and answer

Official answer: 5Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

1. A Min-Heap storing 32 keys is implemented as a complete binary tree (the standard array-based heap representation), meaning every level is fully filled except possibly the last, which is filled left to right.

2. For a complete binary tree of height $h$ (height = maximum number of edges on any root-to-leaf path), the number of nodes $n$ satisfies $2^h\le n\le 2^{h+1}-1$: the minimum occurs when the last level has just 1 node, the maximum when the last level is completely full.

3. We need the $h$ for which $2^h\le 32\le 2^{h+1}-1$.

4. Check $h=5$: the range is $2^5=32$ to $2^6-1=63$. Since $32$ lies in $[32,63]$, $h=5$ satisfies the bound.

5. Check $h=4$: the range is $2^4=16$ to $2^5-1=31$. Since $32\notin [16,31]$, $h=4$ is ruled out.

6. Equivalently, $h=\lfloor {\log }_{2}32\rfloor =\lfloor 5\rfloor =5$, confirming the same result: levels $0$ through $4$ together hold $2^5-1=31$ nodes, so the $32^{\text{nd}}$ node is the sole node on level $5$, giving a root-to-leaf path of $5$ edges.

7. So the height of the Min-Heap $T$ storing 32 keys is $5$.