# Question regarding this proof that a nonempty binary tree with n nodes has height at least $\lfloor log_2 n\rfloor$.

A tree with $$1$$ node has height at least $$0$$, so the claim holds for $$n = 1$$. Now suppose the claim holds for $$n$$. Let $$T$$ be a binary tree with $$n + 1$$ nodes. Select a leaf node and remove it. By our induction hypothesis, the resulting tree has height at least $$\lfloor log_2 n\rfloor$$. If $$n+1$$ is not a power of $$2$$ then this is equal to $$\lfloor log_2 (n+1)\rfloor$$, so we are done. Otherwise, choose a leaf of greatest depth to remove. The resulting tree has height at least $$\lfloor log_2 n\rfloor$$. If the height in fact achieves that, then the only possible tree is the complete binary tree on $$n$$ vertices. Since every internal node has two children, the only place the removed leaf could have come from is from a leaf vertex. Adding a child to any leaf vertex increases the height of the tree by 1. Since$$\lfloor log_2 n\rfloor +1\geq \lfloor log_2 (n+1)\rfloor$$, the claim holds.

I don't understand why we should choose a leaf of the greatest depth to remove, and how if the resulting height equals $$\lfloor log_2 n\rfloor$$ then the only possible tree is a complete binary tree. What if the leaf is not chosen from the greatest depth, or if the height is not equal to $$\lfloor log_2 n\rfloor$$?

Let $$n+1=2^k$$. A tree with height $$\lfloor\log_2{n}\rfloor=k-1$$ and $$2^k-1$$ nodes has to be complete binary since this is the maximum number of nodes you can have for the given height.
Now, if you remove a leaf which is not of greatest depth, then the resulting tree is not going to be complete binary, but it is going to contain $$2^k-1$$ nodes. This means that the height is higher than $$k-1$$, i.e. at least $$k$$, and we are done. The remaining case is when we remove a leaf of greatest depth, which is explained in your solution.
• If I have a complete binary tree with $2^k-1$ nodes, the height is equal to $\lfloor\log_2{(2^k-1)}\rfloor=k-1$. If I add a node to a leaf which is not greatest of depth, the height of the tree is still $k-1$ but isn't $\lfloor\log_2{(n+1)}\rfloor=\lfloor\log_2{(2^k-1+1)}\rfloor=k$ and the lower bound for height becomes higher than the actual height of my tree? Jul 10, 2019 at 20:59