7
$\begingroup$

This question uses the following definition of a complete binary tree:

A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

The following is an excerpt from Algorithms:

It ($\log N$) is also the depth of a complete binary tree with $N$ nodes. (More precisely: $⌊\log N⌋$.)

Why is the above excerpt true?

Originally defined here

$\endgroup$
7
$\begingroup$

Consider how a complete binary tree of height $h$ is constructed, one vertex at the root level, two at the first level below the root, four at the second level below, and so on, until the $h^{th}$ level, which has at least one vertex, but at most twice as many as the previous level. Note that the number of vertices at each level is a power of two (excluding the last, which is a special case). Then we have: $$ 1+\sum_{i=0}^{h-1}2^{i} \leq n \leq \sum_{i=0}^{h}2^{i} $$ Using the identity that the sum of the first $k$ powers of two is $2^{k+1}-1$ we get: $$ 1+2^{h}-1 \leq n \leq 2^{h+1}-1\\ 2^{h} \leq n \leq 2^{h+1}-1 $$ and hence $$ 2^{h} \leq n < 2^{h+1} $$

Taking the base 2 logarithm: $$ h \leq \log n < h+1 $$ So we can conclude $$h = \lfloor\log n\rfloor$$ As $\log n$ is bigger than $h$, but less than the next integer $h+1$.

$\endgroup$
  • 1
    $\begingroup$ It would good to notice that floor(logn) is same as ceiling(log(n+1)) -1. This can also be derived by changing the equality to 2^h -1 < n <= 2^(h+1) -1. $\endgroup$ – KGhatak Jun 7 at 17:48

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.