TAOCP 6.2.3 Exercise 4
Let $I(T)$ denote the internal path length of a tree $T$, defined as the sum of the depths of all internal nodes of $T$, where the root has depth $0$ and each child increases depth by $1$.
Exercise 4. [M22] [M22] Prove or disprove: Among all balanced trees with Fh+1, 1 internal nodes, the Fibonacci tree of order h has the greatest internal path length.
Verified: yes
Solve time: 56s
Solution
Let $I(T)$ denote the internal path length of a tree $T$, defined as the sum of the depths of all internal nodes of $T$, where the root has depth $0$ and each child increases depth by $1$.
Let $T_h$ denote the Fibonacci tree of order $h$, the balanced tree of height $h$ with the minimum possible number of internal nodes, namely $F_{h+1}-1$, constructed by taking subtrees of heights $h-1$ and $h-2$ at every node in the extremal way described in Section 6.2.3.
Let $T$ be any balanced tree with $F_{h+1}-1$ internal nodes and height $h$.
From the proof of Theorem A, any balanced tree of height $h$ satisfies the recurrence inequality
$$ N(T) \ge N(T_{h-1}) + N(T_{h-2}) + 1, $$
with equality if and only if the root has one subtree of height $h-1$ and the other of height $h-2$, and both subtrees attain the minimum possible number of nodes for their respective heights. Since $N(T)=F_{h+1}-1$ equals the minimum number of nodes among all balanced trees of height $h$, equality must hold at the root decomposition.
Hence the root of $T$ has one subtree of height $h-1$ and the other of height $h-2$, and both subtrees are themselves balanced trees with the minimum number of nodes for their heights. Applying the same argument recursively to each subtree yields that every subtree of height $k$ occurring in $T$ must have exactly $F_{k+1}-1$ internal nodes and must split into subtrees of heights $k-1$ and $k-2$ attaining the corresponding minima.
This recursive characterization determines the shape of $T$ uniquely up to interchange of left and right subtrees at nodes where the height pair $(k-1,k-2)$ is assigned to $(\text{left},\text{right})$ or $(\text{right},\text{left})$. Any such interchange preserves all node depths. Therefore every balanced tree with $F_{h+1}-1$ internal nodes has the same multiset of internal node depths as $T_h$.
Since internal path length depends only on these depths, all such trees have identical internal path length:
$$ I(T)=I(T_h). $$
It follows that $T_h$ attains the greatest internal path length among all balanced trees with $F_{h+1}-1$ internal nodes, since no other balanced tree with the same number of nodes can produce a different (and larger) sum of internal node depths.
This completes the proof. ∎