GATE CS 2025 Set 1 Q25 — Binary Heaps

A Min-Heap is represented as a complete binary tree.

The height $h$ of a rooted tree is defined as the maximum number of edges from the root to any leaf node. For a complete binary tree with $N$ nodes, the height $h$ is given by the formula:

Given that the Min-Heap $T$ stores $N = 32$ keys:

Alternative Level-by-Level Verification:

We can determine the level of each node starting from the root at Level 0:

• Level 0: $2^0 = 1$ node (Cumulative total: $1$)
• Level 1: $2^1 = 2$ nodes (Cumulative total: $3$)
• Level 2: $2^2 = 4$ nodes (Cumulative total: $7$)
• Level 3: $2^3 = 8$ nodes (Cumulative total: $15$)
• Level 4: $2^4 = 16$ nodes (Cumulative total: $31$)
• Level 5: $1$ node (Cumulative total: $32$)

Since the $32^{\text{nd}}$ node resides at Level 5, the maximum path length from the root to this leaf node is $5$ edges.

Thus, the height of the Min-Heap $T$ is 5.