8
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – EuYu
    Commented Mar 13, 2013 at 6:53
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Erick Wong
    Commented Mar 13, 2013 at 6:53
  • 2
    $\begingroup$ @Erick Good timing! :) $\endgroup$
    – EuYu
    Commented Mar 13, 2013 at 6:55

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .