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

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?

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.

StackExchange Computer Science Q#6277, answer score: 20