The number of nodes of height h in any n-element heap is atmost:
2022
The number of nodes of height h in any n-element heap is atmost:
- A.
\(n / 2^{h+1}\) - B.
\(\frac{n}{2^{h-1}}\) - C.
\(\frac{n}{2^{h}}\) - D.
\(\frac{n-1}{2^{h-1}}\)
Attempted by 464 students.
Show answer & explanation
Correct answer: A
Answer: The number of nodes of height h is at most ceil(n / 2^{h+1}).
Reasoning (array-index view):
In the array representation of a binary heap (indices 1..n), a node at index i has a descendant at distance h only if 2^{h} * i <= n. Therefore the number of nodes that have a descendant at distance h (i.e., nodes of height at least h) is floor(n / 2^{h}).
The number of nodes of exact height h equals the number of nodes with height at least h minus the number with height at least h+1. That is:
floor(n / 2^{h}) - floor(n / 2^{h+1}).
This difference is upper-bounded by ceil(n / 2^{h+1}). Hence:
number of nodes of height h <= ceil(n / 2^{h+1}).
Example checks: for h = 0 (leaves) this gives ceil(n/2), which matches the usual count of leaves in a heap; for a perfect tree of 2^{k}-1 nodes, it yields the exact counts at each height.
A video solution is available for this question — log in and enroll to watch it.