GATE2025_CS1_Q35

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.

Suppose a Min-Heap T stores 32 keys. The height of T is ______. (Answer in integer)

✅ Final Answer:

The correct answer is 5.

🔹 Short Answer:

A Min-Heap is a complete binary tree. The height h of a complete binary tree with N nodes is given by the formula h = floor(log₂(N)). For N = 32, the height is floor(log₂(32)) = floor(5) = 5.

🔸 Long Answer:

To solve this problem, we need to understand the structural properties of a Min-Heap and the mathematical relationship between the number of nodes and the height of the tree.

Step 1: Understand the Structure of a Min-Heap

A Min-Heap is a specialized tree-based data structure that satisfies the heap property. Structurally, it is always a complete binary tree. This is a crucial piece of information.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Step 2: Relate Height and Number of Nodes (N)

The question defines height as the number of edges from the root to the furthest leaf. Let the height be h. For a complete binary tree of height h, the number of nodes N must be within a specific range:

• A tree of height h has at least 2^h nodes (this occurs if the last level has only one node).
• It has at most 2^(h+1) - 1 nodes (this occurs if all levels up to h are completely full).

This gives us the inequality:

2^h ≤ N < 2^h+1

By taking the base-2 logarithm of all parts, we get:

log₂(2^h) ≤ log₂(N) < log₂(2^h+1)

h ≤ log₂(N) < h + 1

This inequality is the definition of the floor function. Therefore, we can derive the formula for the height h of a complete binary tree with N nodes:

h = floor(log₂(N))

Example: A tree with N=8 nodes has height h = floor(log₂(8)) = 3.

Step 3: Calculate the Height for N = 32

Now we apply the formula with the given number of keys, N = 32.

h = floor(log₂(32))

Since 2⁵ = 32, we know that log₂(32) = 5.

h = floor(5)
h = 5

Therefore, the height of a Min-Heap with 32 keys is 5.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 6: Heapsort).
- Weiss, M. A. (2013). Data Structures and Algorithm Analysis in C++. Pearson. (Chapter 6: Priority Queues (Heaps)).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.