TAOCP 5.3.1 Exercise 20

Section 5.3.1: Minimum-Comparison Sorting

Exercise 20. ▶ [M26] Prove that an extended binary tree has minimum external path length if and only if there is a number $l$ such that all external nodes appear on levels $l$ and $l+1$ (or perhaps all on a single level $l$).

Verified: no
Solve time: 7m08s

Setup

An extended binary tree is a finite rooted tree in which every internal node has exactly two children. The nodes with no children are called external nodes. The depth (or level) of a node is the number of edges on the path from the root to that node; the root has depth 0. The external path length (E(T)) of an extended binary tree (T) is the sum of the depths of all its external nodes. Let (N) be the number of external nodes.

Theorem. An extended binary tree (T) with (N) external nodes has minimum possible external path length among all extended binary trees with (N) external nodes if and only if there exists an integer (l) such that every external node of (T) has depth either (l) or (l+1) (or all have depth (l)).

Solution

We prove the equivalence by showing that any tree violating the level condition can be transformed into another tree with the same (N) but strictly smaller external path length. Consequently, the trees satisfying the condition are exactly those that achieve the minimum.

Preliminaries: Kraft equality

For any extended binary tree, [ \sum_{v \text{ external}} 2^{-\text{depth}(v)} = 1. ] This is easily proved by induction: a single external node (the root) satisfies (2^0=1); replacing an external node at depth (d) by an internal node with two external children at depth (d+1) changes the sum by (-2^{-d}+2\cdot 2^{-(d-1)}=0).

Necessity (minimum (\Rightarrow) balanced levels)

Assume (T) has minimum external path length among all extended binary trees with (N) external nodes. Suppose, for contradiction, that the external nodes are not all on at most two adjacent levels. Let (d_{\min}) be the minimum depth of an external node and (d_{\max}) the maximum depth; then (d_{\max} \ge d_{\min}+2).

Consider a deepest internal node (p). Because (p) has maximum depth among internal nodes, both of its children are external; denote their common depth by (d_{\max}). Thus (p) is at depth (d_{\max}-1). Also choose an external node (u) at depth (d_{\min}).

Since (d_{\max} \ge d_{\min}+2), we have (d_{\max}-1 \ge d_{\min}+1). Hence (p \neq u) and (p) cannot be an ancestor of (u) (otherwise (u) would lie in the subtree of (p) and would have depth (\ge d_{\max}), contradicting (d_{\min} \le d_{\max}-2)).

Now construct a new extended binary tree (T') from (T) by the following exchange:

Remove the two children of (p), making (p) an external node.
Replace (u) by an internal node with two external children (i.e., add two children to (u)).

The number of external nodes remains (N) (we lose two and gain two). Every internal node still has exactly two children, so (T') is a valid extended binary tree.

Compute the change in external path length:

Removing the cherry at depth (d_{\max}): (-2d_{\max} + (d_{\max}-1) = -d_{\max}-1).
Adding a cherry at depth (d_{\min}): (-d_{\min} + 2(d_{\min}+1) = d_{\min}+2). Total change: (\Delta E = (d_{\min}+2) + (-d_{\max}-1) = d_{\min} - d_{\max} + 1 \le -1).

Thus (E(T') < E(T)), contradicting the minimality of (T). Therefore (d_{\max} - d_{\min} \le 1); all external nodes lie on levels (l) and (l+1) for some (l) (or all on a single level (l)).

Sufficiency (balanced levels (\Rightarrow) minimum)

Suppose (T) has (N) external nodes, all at depths (l) and (l+1) (with the understanding that if all are at depth (l) we simply have (b=0) below). Let (a) be the number of external nodes at depth (l) and (b) the number at depth (l+1). By the Kraft equality, [ \frac{a}{2^l} + \frac{b}{2^{l+1}} = 1 \quad\Longrightarrow\quad 2a + b = 2^{l+1}. ] Together with (a+b = N) we obtain [ a = 2^{l+1} - N,\qquad b = 2N - 2^{l+1}. ] Nonnegativity of (a,b) forces (2^l \le N \le 2^{l+1}). The external path length of (T) is [ E(T) = a l + b(l+1) = lN + b = N(l+2) - 2^{l+1}. ] This value depends only on (N) (when (N) is a power of two, both (l = \log_2 N) and (l = \log_2 N - 1) give the same result). Denote this common value by (E^*(N)).

Now take any extended binary tree (T') with (N) external nodes. If (T') satisfies the level condition, then (E(T') = E^(N)). If (T') violates the condition, the exchange construction used in the necessity proof produces a tree (T'') with the same (N) and (E(T'') < E(T')). Repeating this process (which must terminate because external path length is a non‑negative integer and strictly decreases at each step) we eventually reach a tree satisfying the condition, whose external path length is (E^(N)). Hence (E(T') > E^*(N)) for every tree violating the condition.

Therefore the trees with minimum external path length are exactly those whose external nodes all lie on two adjacent levels (or one level). ∎

Verification

The critical step is the exchange transformation. We verify it on a concrete non‑optimal tree to ensure no hidden assumptions.

Example. Let (N=5). The optimal tree has depths ({2,2,2,3,3}) (here (l=2), (a=3), (b=2), (E=12)). Consider a non‑optimal tree with depths ({1,3,3,3,3}) (e.g., a root with one leaf at depth 1 and a subtree of 4 leaves at depth 3). Here (d_{\min}=1), (d_{\max}=3). The deepest internal node (p) is the parent of the four leaves at depth 3; its children are two external nodes at depth 3? Wait, if there are four leaves at depth 3, the internal node (p) could be the parent of two of them (a cherry at depth 3). Choose (p) as such a parent (depth 2). The shallow leaf (u) is at depth 1. Apply the exchange:

Remove the cherry at (p) (two leaves at depth 3) (\to) (p) becomes a leaf at depth 2.
Replace (u) (depth 1) by a cherry (two leaves at depth 2). New depths: we lose two 3’s, gain one 2, lose one 1, gain two 2’s. The new multiset is ({2,2,2,2,3})? Original: one 1, four 3’s. After exchange: one 2 (from (p)), two 2’s (from (u)), and the remaining two 3’s. Result: three 2’s and two 3’s, which is the optimal configuration. Change in (E): original (1+3+3+3+3=13); new (2+2+2+2+3=11). The formula gives (\Delta E = d_{\min}-d_{\max}+1 = 1-3+1 = -1), matching the decrease from 13 to 12? Wait, the new sum is 11? Let's recalc: original depths: 1,3,3,3,3 sum=13. After exchange: p was at depth 2 with two children at depth 3. We remove those two 3's and make p a leaf at depth 2. u was at depth 1, we make it internal with two children at depth 2. So we remove the 1 and add two 2's. The remaining leaves: the other two 3's (since there were four 3's total, we removed two). So new depths: 2 (p), 2,2 (from u), 3,3. Sum = 2+2+2+3+3 = 12. Yes, 12. The decrease is 1. The optimal sum is 12. The transformation worked perfectly.

The transformation requires a deepest internal node with two external children. Such a node always exists because the tree is finite and has at least one internal node (if (N\ge 2); for (N=1) the condition holds trivially). The choice of (p) as a deepest internal node guarantees its children are external. The argument that (p) is not an ancestor of (u) holds because if (p) were an ancestor of (u), then (u) would be in the subtree of (p), but (p)’s children are leaves at depth (d_{\max}), so (u) would have depth (d_{\max}), contradicting (d_{\min} \le d_{\max}-2). Hence the two modifications are on disjoint parts of the tree and the resulting structure is a valid extended binary tree.

The process terminates because (E) is a non‑negative integer and strictly decreases at each step. Thus any tree not satisfying the condition can be strictly improved, proving that the condition is both necessary and sufficient for minimum external path length.

Notes

The same exchange argument underlies the proof that Huffman coding produces optimal prefix codes, and it shows that the minimum external path length for (N) external nodes is [ E^(N) = N\bigl(\lfloor\log_2 N\rfloor+2\bigr) - 2^{\lfloor\log_2 N\rfloor+1}, ] which is equivalent to the formula (E^(N) = N\lceil\log_2 N\rceil - 2^{\lceil\log_2 N\rceil} + N) given in the text.