TAOCP 5.3.1 Exercise 21

Section 5.3.1: Minimum-Comparison Sorting

Exercise 21. [M21] The height of an extended binary tree is the maximum level number of its external nodes. If $x$ is an internal node of an extended binary tree, let $t(x)$ be the number of external nodes below $x$, and let $l(x)$ denote the root of $x$'s left subtree. If $x$ is an external node, let $t(x) = 1$. Prove that an extended binary tree has minimum height among all binary trees with the same number of nodes if

$$\left|t(x) - 2t(l(x))\right| \le 2^{\lceil \lg t(x) \rceil} - t(x)$$

for all internal nodes $x$.

Verified: no
Solve time: 52s

---

Solution

Let (T) be an extended binary tree. For any node (x) in (T), let (t(x)) denote the number of external nodes in the subtree rooted at (x) (for an external node (x), (t(x)=1)). If (x) is an internal node, let (l(x)) be the root of its left subtree and (r(x)) the root of its right subtree; then (t(x)=t(l(x))+t(r(x))). The height (h(x)) of the subtree rooted at (x) is the maximum level number of its external nodes (with the root at level 0). Thus (h(x)=0) for an external node, and (h(x)=1+\max(h(l(x)),h(r(x)))) for an internal node.

The minimum possible height of any extended binary tree with (n) external nodes is (\lceil\lg n\rceil), because a tree of height (h) can contain at most (2^h) external nodes. We shall prove that if (T) satisfies the condition

[ \bigl|,t(x)-2,t(l(x)),\bigr| ;\le; 2^{\lceil\lg t(x)\rceil}-t(x) \qquad\text{for every internal node }x, ]

then (h(x)\le\lceil\lg t(x)\rceil) for every node (x); in particular (h(T)=h(\text{root})=\lceil\lg t(\text{root})\rceil), so (T) has minimum height among all extended binary trees with the same number of external nodes (and therefore the same total number of nodes, which is (2n-1)).

Lemma

For an internal node (x) with (t=t(x)\ge 2) and (L=\lceil\lg t\rceil), the given inequality is equivalent to

[ t(l(x))\le 2^{L-1}\quad\text{and}\quad t(r(x))\le 2^{L-1}. ]

Proof. Let (t_L=t(l(x))) and (t_R=t(r(x))=t-t_L). The inequality reads

[ |t-2t_L|\le 2^L-t. ]

Expanding the absolute value gives

[ t-2^L ;\le; 2t_L-t ;\le; 2^L-t. ]

The right‑hand part yields (2t_L\le 2^L), i.e. (t_L\le 2^{L-1}). The left‑hand part yields (2t-2^L\le 2t_L), i.e. (t_L\ge t-2^{L-1}). Using (t_R=t-t_L), the lower bound on (t_L) becomes (t_R\le 2^{L-1}). Because the expression (|t-2t_L|) is symmetric in (t_L) and (t_R), the same bounds follow directly from the condition. ∎

Inductive Proof of Height Bound

We prove by induction on (t(x)) that (h(x)\le\lceil\lg t(x)\rceil) for every node (x).

Base case: If (x) is external, (t(x)=1) and (h(x)=0=\lceil\lg 1\rceil).

Inductive step: Let (x) be an internal node and set (t=t(x)), (L=\lceil\lg t\rceil). By the lemma, both (t(l(x))) and (t(r(x))) are at most (2^{L-1}). Hence

[ \lceil\lg t(l(x))\rceil \le L-1,\qquad \lceil\lg t(r(x))\rceil \le L-1. ]

By the induction hypothesis,

[ h(l(x))\le\lceil\lg t(l(x))\rceil,\qquad h(r(x))\le\lceil\lg t(r(x))\rceil. ]

Therefore

[ h(x)=1+\max\bigl(h(l(x)),h(r(x))\bigr) \le 1+\max\bigl(\lceil\lg t(l(x))\rceil,\lceil\lg t(r(x))\rceil\bigr) \le 1+(L-1)=L=\lceil\lg t\rceil. ]

This completes the induction.

Applying the bound to the root gives (h(T)=h(\text{root})\le\lceil\lg t(\text{root})\rceil). Since any extended binary tree with (t(\text{root})) external nodes must have height at least (\lceil\lg t(\text{root})\rceil), equality holds. Thus (T) has minimum possible height.

This completes the proof. ∎