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
    Commented Oct 31, 2012 at 23:13
  • $\begingroup$ Is it assumed that the tree is balanced? $\endgroup$
    – Joe
    Commented Nov 1, 2012 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
    Commented Nov 1, 2012 at 1:54

2 Answers 2


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
    Commented Nov 2, 2012 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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