# Maximum number of nodes with height h

How is $\frac{n}{2^{h+1}}$ the maximum possible number of nodes at height $h$ for a binary search tree or heap tree? I saw this as proof to asymptotically bound the build_heap function in the book, but I don't get it.

• What book? What have you tried? Also, the answer is likely "It just is, here's a proof." Try proving and/or finding a counter-example!
– Raphael
Oct 31 '12 at 23:13
• Is it assumed that the tree is balanced?
– Joe
Nov 1 '12 at 0:42
• It doesn't matter if the tree is balanced or not; this is just the maximum possible number of nodes. Nov 1 '12 at 1:54

I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from the node to a leaf, such that the height of a leaf is 0 (and the height of the root is the height of the tree). So for a leaf, $\frac{n}{2^{0+1}}=n/2$. For the root, $h=\log_2 n$, so $\frac{n}{2^{\log_2 n+1}}=n/n=1$. And the rest of the tree follows from there.

I think it should be a full binary tree to support maximum number of nodes at a particular height.

A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.

At successive level, number of nodes would be $1, 2, 4, 8,\ldots,n/2$.

For $h=0$, nodes = $\frac{n}{2^{0+1}} = \frac n2$.

For $h=\log_2n$, nodes = $\frac{n}{2^{\log_2n+1}} = 1$.

• Usually a 2-tree means something else. Nov 2 '12 at 8:19