Problem Detail: 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))$
$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))$
Asked By : uritz.shara
Answered By : Shaull
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-1in theta(2x-1)$, and in particular, $x-1in omega(log(2x-1))$, so $Hnotin O(log N)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10507
