3
$\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
  • 6
    $\begingroup$ Perhaps you mean a complete binary tree? The names are alike, but a complete tree is balanced, and certainly has the $\log$ property. $\endgroup$ Mar 13, 2013 at 8:24
  • $\begingroup$ Yes, there are many different names around that are sometimes used interchangeably, especially when texts are translated. $\endgroup$
    – Raphael
    Mar 13, 2013 at 14:40
  • $\begingroup$ I explained it here: stackoverflow.com/a/13093274/550393 $\endgroup$ Apr 10, 2014 at 15:41

1 Answer 1

4
$\begingroup$

Your claim is incorrect (which might make it really hard to prove...) Indeed, as you describe, you can have a full binary tree of height $O(n)$: Let every right child be a leaf, and every left child have 2 children, until some level in which it has two leaf-children.

It holds that $x-1\in \theta(2x-1)$, and in particular, $x-1\in \omega(\log(2x-1))$, so $H\notin O(\log N)$.

$\endgroup$

Your Answer

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

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