# Number of nodes of given height in binary heap

Show that there are at most $$\lceil n/2^{h+1}\rceil$$ nodes of height $$h$$ in any $$n$$-element binary heap.

How can I show this? Or, how can I prove this?

• Where is that exercise from? Please cite the sources... Apr 20, 2020 at 13:21
• This is Exercise 6.3-3 in CLRS. Apr 20, 2020 at 14:17
• Please credit the original source of all copied material, in the question. Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX.
– D.W.
Apr 20, 2020 at 17:56
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
Apr 20, 2020 at 17:56

Suppose towards a contradiction that your heap $$H$$ contains at least $$\lceil n/2^{h+1} \rceil + 1$$ nodes of height $$h$$, for some choice of $$h$$.

At least $$\lceil n/2^{h+1} \rceil$$ of these nodes are the roots of a complete binary subtree of the heap. Therefore each of these subtrees contains $$\sum_{i=0}^h 2^i = 2^{h+1}-1$$ nodes.

The subtree of $$H$$ rooted in any of the remaining nodes of height $$h$$, contains at least $$1$$ vertex (stronger lower bounds are possible, but this is all we need).

Since the subset of nodes having height at least $$h$$ in $$H$$ induces a binary tree $$T$$ whose leaves are the nodes of height exactly $$h$$ in $$H$$, we know that $$T'$$ must have at least $$\lceil n/2^{h+1} \rceil + 1 - 1$$ internal nodes. This means that the number of nodes of height larger than $$h$$ in $$H$$ is at least $$\lceil n/2^{h+1} \rceil$$.

Then, the total number $$n$$ of nodes in $$T$$ must be at least:

\begin{align*} n \ge \lceil n/2^{h+1} \rceil \cdot (2^{h+1}-1) + \lceil n/2^{h+1} \rceil + 1 = \lceil n/2^{h+1} \rceil \cdot 2^{h+1} + 1 \ge n + 1. \end{align*}