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 Answer 1

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.

$\endgroup$
2
  • $\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
    Commented Jul 10, 2019 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
    Commented Jul 10, 2019 at 21:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .