TAOCP 5.4.9 Exercise 12
Let $T$ be a rooted tree with $n>0$ leaves, and let the degree path length $(6)$ be defined as in Section 5.
Section 5.4.9: Disks and Drums
Exercise 12. [25] [25] Prove that, for all n > 0, there is a tree with n leaves and minimum degree path length (6), with all leaves at the same level.
Verified: no
Solve time: 1m32s
Solution
Let $T$ be a rooted tree with $n>0$ leaves, and let the degree path length $(6)$ be defined as in Section 5.4.4, namely
$$ D(T)=\sum_{x \in L(T)} d(x), $$
where $L(T)$ is the set of leaves of $T$ and $d(x)$ is the depth of leaf $x$.
Fix $n>1$ first. For every leaf $x \in L(T)$, the root lies on every root-to-$x$ path, hence $d(x)\ge 1$. Summing over all leaves yields
$$ D(T)=\sum_{x \in L(T)} d(x) \ge \sum_{x \in L(T)} 1 = n. $$
Construct a tree $T_0$ consisting of a root node joined directly to $n$ leaves. Every leaf of $T_0$ has depth $1$, hence
$$ D(T_0)=\sum_{x \in L(T_0)} 1 = n. $$
The inequality $D(T)\ge n$ for all $T$ with $n$ leaves and the equality $D(T_0)=n$ imply that $T_0$ attains the minimum possible degree path length. Every leaf of $T_0$ lies at the same level.
For $n=1$, the single-vertex tree has one leaf at depth $0$, and it trivially satisfies the same property.
The constructed tree therefore has $n$ leaves, achieves minimum degree path length $(6)$, and has all leaves at the same level for all $n>0$.
This completes the proof. ∎