TAOCP 2.3.4.5 Exercise 1
The internal path length of a binary tree is the sum of the depths of its $n$ internal nodes.
Exercise 1. [**] [12] Are there any other binary trees with 12 internal nodes and minimum path length, besides the complete binary tree (5)?
Verified: yes
Solve time: 1m22s
The internal path length of a binary tree is the sum of the depths of its $n$ internal nodes. A minimum is achieved when the multiset of depths is lexicographically minimized under the constraint that at depth $k$ there are at most $2^k$ nodes. For $n=12$ this forces the unique level counts
$$ 1,\ 2,\ 4,\ 5 $$
at depths $0,1,2,3$ respectively, since $1+2+4=7$ and $12-7=5$, while no deeper level is required.
Any tree achieving this minimum must place all internal nodes at depths $0,1,2,3$ with no node at depth $\ge 4$, and each node at depth $k$ has two ordered child positions at depth $k+1$ when those positions are filled. At depth $3$ there are $8$ available child positions (two under each of the $4$ nodes at depth $2$), and exactly $5$ of these positions must be occupied by internal nodes. Every choice of $5$ such positions yields a valid ordered tree, since each chosen position corresponds to exactly one child of a specified parent and no node receives more than two children.
Each such tree has identical internal path length, since all internal nodes occur at the same multiset of depths $0,1,2,3$, so the sum of depths is unchanged. These trees are not all identical as ordered trees, since different selections of the $5$ depth-$3$ positions distribute leaves among different parents.
This completes the proof. ∎