Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Merbs Nov 1 '12 at 1:54
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you Merbs n.n. –  user1675999 Nov 4 '12 at 16:25
add comment

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$.

share|improve this answer
2  
Usually a 2-tree means something else. –  A.Schulz Nov 2 '12 at 8:19
    
Thank you Shashwat :D. –  user1675999 Nov 4 '12 at 16:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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