HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Height of a full binary tree

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fullbinarytreeheight

Problem

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

Solution

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

Context

StackExchange Computer Science Q#10507, answer score: 4

Revisions (0)

No revisions yet.