TAOCP 5.3.1 Exercise 22

We prove that an extended binary tree has minimum external path length among all extended binary trees with the same number \(N\) of external nodes **iff** for every internal node \(x\) \[ |t(x)-2\,t(...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.1: Minimum-Comparison Sorting

Exercise 22. [M24] Continuing exercise 21, prove that a binary tree has minimum external path length among all binary trees with the same number of nodes if and only if

$$|t(x) - 2t(l(x))| \le 2^{\lceil \lg t(x) \rceil} - t(x) \quad \text{and} \quad |t(x) - 2t(l(x))| \le t(x) - 2^{\lfloor \lg t(x) \rfloor}$$

for all internal nodes $x$. [Thus, for example, if $t(x) = 67$, we must have $t(l(x)) = 32$, 33, 34, or 35. If we merely wanted to minimize the height of the tree we could have $3 \le t(l(x)) \le 64$, by the preceding exercise.]

Verified: no
Solve time: 10m03s

Solution

We prove that an extended binary tree has minimum external path length among all extended binary trees with the same number (N) of external nodes iff for every internal node (x)

[ |t(x)-2,t(l(x))|;\le;2^{\lceil\lg t(x)\rceil}-t(x) \qquad\text{and}\qquad |t(x)-2,t(l(x))|;\le;t(x)-2^{\lfloor\lg t(x)\rfloor}, \tag{*} ]

where (t(x)) is the number of external nodes in the subtree rooted at (x) and (l(x)) is the root of its left subtree (for an external node (t(x)=1)).

By Exercise 20, a tree has minimum external path length iff all its external nodes lie on two adjacent levels (l) and (l+1) (or all on one level (l)). We will show that this global condition is equivalent to the local condition ((*)).

Notation

Let (N) be the total number of external nodes. Write (N=2^l+m) with (0\le m<2^l); then (l=\lfloor\lg N\rfloor) (if (m=0) we also have (l=\lg N)). For an internal node (x) set (N_x=t(x)) and (L_x=t(l(x))). The right subtree size is (R_x=N_x-L_x). The condition ((*)) for (x) becomes

[ |N_x-2L_x|;\le;2^{\lceil\lg N_x\rceil}-N_x \quad\text{and}\quad |N_x-2L_x|;\le;N_x-2^{\lfloor\lg N_x\rfloor}. ]

If (N_x=2^{l_x}) (a power of two) both bounds are zero, forcing (L_x=N_x/2). If (N_x) is not a power of two, let (l_x=\lfloor\lg N_x\rfloor) and (m_x=N_x-2^{l_x}); then the bounds are (2^{l_x+1}-N_x=2^{l_x}-m_x) and (N_x-2^{l_x}=m_x), so ((*)) is equivalent to

[ |N_x-2L_x|;\le;\min(m_x,,2^{l_x}-m_x). \tag{1} ]

1. ((*);\Rightarrow;) all leaves on levels (l) and (l+1) (or all on (l))

We prove this by induction on (N).

Base cases. (N=1) (single external node) and (N=2) (two leaves at depth 1) satisfy the global condition trivially.

Inductive step. Assume the statement holds for all trees with fewer than (N) external nodes. Consider a tree (T) with (N) leaves that satisfies (()). Let the root have left size (L) and right size (R=N-L). By (()) at the root we have (1) with (l_x=l) and (m_x=m). This inequality is easily solved:

  • if (m\le 2^{l-1}) then (L\in[2^{l-1},,2^{l-1}+m]);
  • if (m>2^{l-1}) then (L\in[m,,2^l]).

In both cases (L) and (R) lie in the interval ([2^{l-1},,2^l]). Hence (\lfloor\lg L\rfloor) and (\lfloor\lg R\rfloor) are either (l-1) or (l).

By the induction hypothesis the left and right subtrees satisfy the global condition: their external nodes all lie on two adjacent levels (\ell) and (\ell+1) (or all on (\ell)) where (\ell=\lfloor\lg L\rfloor) and (\lfloor\lg R\rfloor) respectively. Attaching these subtrees to the root increases all depths by one. We must verify that the resulting leaves all lie on levels (l) and (l+1) (or all on (l) when (m=0)).

  • If (m=0) then (N=2^l) and ((*)) forces (L=R=2^{l-1}). Both subtrees are full trees with all leaves at depth (l-1); after adding the root all leaves are at depth (l).
  • If (m>0) then (L,R\in[2^{l-1},2^l]).
    • If (L=2^l) (which implies (m=2^{l-1}) and (R=2^{l-1})), the left subtree has all leaves at depth (l), the right subtree at depth (l-1); overall depths become (l+1) and (l).
    • If (R=2^l) the situation is symmetric.
    • Otherwise both (L) and (R) are strictly between (2^{l-1}) and (2^l), so (\lfloor\lg L\rfloor=\lfloor\lg R\rfloor=l-1). Each subtree has leaves on levels (l-1) and (l); adding the root moves them to levels (l) and (l+1).

In every case the whole tree has all external nodes on levels (l) and (l+1). This completes the induction.

2. all leaves on levels (l) and (l+1) (\Rightarrow;(*)

Again we use induction on (N).

Base cases. (N=1,2) are trivial.

Inductive step. Let (T) be a tree with (N) external nodes all at depths (l) and (l+1) (or all at (l)). Write (N=2^l+m) with (0\le m<2^l). Let the left subtree have (L) external nodes and the right subtree (R=N-L). The leaves of the left subtree are at depths (l-1) and (l) (or all at one of these levels); similarly for the right subtree. By the induction hypothesis both subtrees satisfy ((*)) for their internal nodes. It remains to check the root.

Denote by (L_l) the number of leaves in the left subtree that are at depth (l) (i.e., at overall depth (l+1)), and by (R_l) the analogous number for the right subtree. Because the left subtree is a minimum‑external‑path‑length tree of size (L) with leaves on levels (l-1) and (l), we have the well‑known relation

[ L = 2^{l-1} + \frac{L_l}{2}, \qquad 0\le L_l\le 2^l,; L_l\text{ even}. ]

(If (L=2^{l-1}) all leaves are at level (l-1) so (L_l=0); if (L=2^l) all leaves are at level (l) so (L_l=2^l); if (2^{l-1}<L<2^l) the subtree has exactly (2(L-2^{l-1})) leaves at level (l).) The same holds for the right subtree: (R = 2^{l-1} + R_l/2). Summing gives

[ N = L+R = 2^l + \frac{L_l+R_l}{2}. ]

But we also know (N=2^l+m); therefore (L_l+R_l = 2m). Now compute

[ N-2L = R-L = \frac{R_l-L_l}{2}. ]

The condition ((*)) for the root is exactly (|R_l-L_l|/2 \le \min(m,,2^l-m)). Because (0\le L_l,R_l\le 2^l) and (L_l+R_l=2m), the maximum possible value of (|R_l-L_l|) is

  • (2m) if (2m\le 2^l) (then we can take (L_l=2m, R_l=0));
  • (2(2^l-m)) if (2m>2^l) (then one of them must be at most (2^l) and the other (2m-2^l)).

In both cases (|R_l-L_l|/2 \le \min(m,,2^l-m)). Hence the root satisfies (()). By induction the whole tree satisfies (()).

3. Equivalence with minimum external path length

Exercise 20 proves that a tree has minimum external path length iff its external nodes all lie on two adjacent levels (or all on one level). We have just shown that this global property is equivalent to the local condition (()). Therefore a tree has minimum external path length iff it satisfies (()) for every internal node (x). ∎

Notes

The proof uses the characterization from Exercise 20 as a bridge. The key step is translating the global “two‑level” condition into the local bounds on (L_x). The relation (L = 2^{l-1}+L_l/2) for a subtree with leaves on levels (l-1) and (l) is fundamental; it reflects the fact that every time we replace a leaf at level (l-1) by an internal node we gain two leaves at level (l), increasing the leaf count by one while keeping the tree optimal.