Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far:

I am considering the worst case of a full binary tree in which each right node has a subtree, and each left node is a leaf. In this case:
$N = 2x - 1$
$H = x - 1$
I am going nowhere trying to prove that $H = O(log(N))$

Furthermore, we know that leaves l is bounded by $h+1 <l<2^h$.
Internal nodes is bounded by $h<i<2^{h-1}$.
All this proves is that number of nodes $n=i+e$ is $<= 2^{h+1} - 1$ i.e. $log(n) <= h$. But this does not take me anywhere closer to prove that $H = O(log(n))$

share|improve this question
1  
The height of the tree is bounded below logarithmically, but not above (in fact, you've shown that $H=\mathcal{O}(n)$). Are you sure the problem is right? This holds for a complete binary tree though. Is that what you meant? –  EuYu Mar 13 '13 at 6:53
2  
Your worst case shows explicitly that $h$ is not $O(\log n)$ for an arbitrary full binary tree. You need another assumption such as "all leaves have about the same depth" before it's true that $h = O(\log n)$. –  Erick Wong Mar 13 '13 at 6:53
1  
@Erick Good timing! :) –  EuYu Mar 13 '13 at 6:55
add comment

1 Answer

Given h...height if tree, N(h).. count of nodes for tree height h. If h = 1: N(h) = 1; h = 2: N(h) = N(1) * 2 = 1 * 2; h = 3: N(h) = N(2) * 2 = N(1) * 2 * 2 = 1 * 2 * 2 * 2; ... h = n: N(n) = N(n-1) * 2 = ... = 1 * 2 * 2 * 2...= 1 * 2^n = 2^n Each node has two children.

So, count of nodes if height of tree is n is N(n) = 2^n. And if count of nodes of full binary tree is N, then height of tree n is proportional to log_2(N) or n = C(log(N)).

share|improve this answer
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.