# Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children.

I read that if such a tree has $n$ nodes, then its depth is $\lfloor\log_2n\rfloor$, which is an interesting statement that I would like to understand.

I have tried to prove it to myself by using induction and I do see that it holds for $n=2$ (and $3$), but the floor function together with the logarithm presents some difficulties to me in the use of induction. Could anybody prove why the depth of such a tree is $\lfloor\log_2n\rfloor$? I thank you very much!

It’s easier to understand if you word backwards. Suppose that such a tree has depth $d$; what are the maximum and minimum possible numbers of nodes? A perfect binary tree of depth $d$ has
$$1+2+\ldots+2^d=2^{d+1}-1$$
nodes; that’s clearly the maximum. You can remove at most $2^{d-1}$ of the nodes in the last level and still have a quasi-complete binary tree of depth $d$, so the minimum is
$$2^{d+1}-1-(2^d-1)=2^d\;.$$
With fewer than $2^d$ nodes you can’t reach a depth of $d$, and with more than $2^{d+1}-1$ you’re forced deeper. Thus $n$, the number of nodes, must satisfy $2^d\le n\le 2^{d+1}-1$, or simply $2^d\le n<2^{d+1}$. Take logs base $2$, and you get $d\le\log_2n<d+1$, which is exactly the meaning of $\lfloor\log_2n\rfloor=n$.
• Wow: what a clear enlightening answer! $\infty$ thanks!!! – Self-teaching worker Jan 25 '15 at 0:05