Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

Question

In my Java class, we are learning about complexity of different types of collections.

Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height of a binary tree is $\log_2(n+1) - 1$, but doesn't offer further explanation.

Can someone explain why?

Answer 1

A binary tree has 1 or 2 children at non-leaf nodes and 0 nodes at leaf nodes. Let there be $n$ nodes in a tree and we have to arrange them in such a way that they still form a valid binary tree.

Without proving, I am stating that to maximize the height, given nodes should be arranged linearly, i.e. each non-leaf node should have only one child:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Here, formula to compute relation of height in terms of number of nodes is straight-forward. If $h$ is the height of the tree, then $h = n-1$.

Now, if we try to construct a binary tree of $n$ nodes with minimum height (always reducible to a complete binary tree), we have to pack as many nodes as possible in upper levels, before moving on to the next level. So, the tree takes the form of following tree:

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Let us start with a particular case, $n = 2^m - 1$.

We know that, $$ 2^0 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1 $$

Also, it is easy to prove that, a level $i$ can have at most $2^i$ nodes in it.

Using this result in the above sum, we find that for each level $i$, from $0$ to $m$, there exists a corresponding term $2^{i-1}$ in the expansion of $2^m - 1$. This implies, that a complete binary tree $2^m - 1$ nodes is completely filled and has height, $h(2^m-1) = m-1$, where $h(n) = $ height of a complete binary tree with $n$ nodes.

Using this result, $h(2^m) = m$, since tree with $2^m-1$ nodes is completely filled and thus a tree with $(2^m-1)+1 = 2^m$ nodes has to accomodate the extra node in the next level $m$, increasing the height by 1 from $m-1$ to $m$.

Until now we have proved, $$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ as well as, $$h(2^{m+1} -1) = m$$

Thus, $\forall n \in \mathbb{Z}, 2^m \leq n < 2^{m+1}$ $$m \leq h(n) < m+1$$

But, taking log (base 2) on both sides, $$m \leq \log_2(n) < m+1$$ $$m = \lfloor \log_2(n) \rfloor$$

Thus, $\forall n, n \in [2^m, 2^{m+1})$ $$h(n) = m = \lfloor \log_2(n) \rfloor$$

And we can generalize this result $\forall n \in \mathbb{Z}$ using induction.

PS: The book that states height of a complete binary tree as $\log_2(n+1)-1$ is not valid for all $n$ because $\log_2(n)$ would give non-integral values for most integers $n$ (i.e. for all but perfect binary trees), but height of a tree is purely integral.

Answer 2

I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then all nodes on the parent tier must have two children.

So a fully saturated binary tree with $4$ tiers will have $1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$ nodes maximum and will have a depth of $3$. Thus if we have the depth of a binary tree, we can very easily find the maximum number of nodes (which occurs when the tree is fully saturated). If you recall from your algebra classes this is just a geometric series and can therefore be represented like this:

$$ \text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}. $$

So let's rearrange: $$ \text{nodes}=2^{\text{depth}+1}-1, $$ then solve for the depth: \begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray} and there's your formula. Now keep in mind this only yields integer values when the every tree is completely filled up (a 'perfect' binary tree) so if you get a non-integer value, remember to round up.

Answer 3

To keep the height minimum, it is easy to see that we need to fill all the levels except possibly the last. Why? otherwise, we could just move up the last level nodes into empty slots in the upper levels.

Now, imagine that I have some unspecified number of beans and I give you one bean at a time and ask you to construct a binary tree with minimum height possible. I might run of out beans by the time either you filled up the last level completely or at least have one bean in the last level. Let us say, you have your tree height h at this point.

In either case, h doesn't change. So which means you have a complete binary tree of height h with my constraint. But I assumed imaginary beans in the last level (if you couldn't fill the last level). So it is actually, $$ 2^{0}+2^{1}+2^{2}+2^{3}+\dots+2^{h}=2^{h+1}-1 \leq n\,. $$ So minimum $$h = \lg(n+1)-1\,.$$ But apply ceiling since we are adding imaginary beans and not deleting them.