Question

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).

Hint:

In a complete binary tree, the height is the number of edges from the root to the deepest leaf. The height is approximately \( \log_2 n \), where \( n \) is the number of nodes.

Answer 1

Correct Answer: 5

A Min-Heap is a specific type of complete binary tree where the value of each node is less than or equal to the values of its children, and all levels are filled from left to right.The height of a binary tree represents the number of edges from the root to the furthest leaf. For a heap containing $n$ elements, we can determine the height by observing the relationship between the total number of nodes and the levels of the tree.

---

Step 1: Use the logarithmic relationship of nodes to height

The height $h$ of a complete binary tree with $n$ nodes is given by the floor of the base-2 logarithm of $n$:

$h = \lfloor \log_2(n) \rfloor$

Given $n = 32$, we substitute the value into the equation:

$h = \lfloor \log_2(32) \rfloor$

---

Step 2: Solve for h

Since $2^5 = 32$, the exact value of $\log_2(32)$ is $5$.

$h = \lfloor 5 \rfloor = 5$

---

Step 3: Verify via level capacity

A tree of height $h$ can hold a maximum of $2^{h+1} - 1$ nodes.If the height were 4, the max nodes would be $2^5 - 1 = 31$.Since we have 32 nodes, we have just started the next level, meaning the longest path now consists of 5 edges.

---

Final Answer:

The height of the Min-Heap storing 32 keys is 5.