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$
  • 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$ – Hendrik Jan Mar 13 '13 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 '13 at 14:40
  • $\begingroup$ I explained it here: stackoverflow.com/a/13093274/550393 $\endgroup$ – 2cupsOfTech Apr 10 '14 at 15:41
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, privacy policy and cookie policy

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