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.

  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Oct 31 '12 at 23:13
  • $\begingroup$ Is it assumed that the tree is balanced? $\endgroup$ – Joe Nov 1 '12 at 0:42
  • $\begingroup$ It doesn't matter if the tree is balanced or not; this is just the maximum possible number of nodes. $\endgroup$ – Merbs 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$.

  • 2
    $\begingroup$ Usually a 2-tree means something else. $\endgroup$ – A.Schulz Nov 2 '12 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.