3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Wow: what a clear enlightening answer! $\infty$ thanks!!! $\endgroup$ – Self-teaching worker Jan 25 '15 at 0:05
  • 2
    $\begingroup$ @Self-teachingDavide: You're very welcome. $\endgroup$ – Brian M. Scott Jan 25 '15 at 0:13

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.