1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yandle Jul 10 '19 at 20:59
  • $\begingroup$ In a complete binary tree all leaves have the same depth. If you add a node to any of them, you have increased the height of the tree by 1. $\endgroup$ – EuxhenH Jul 10 '19 at 21:35

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.