TAOCP 2.3.4.5 Exercise 9
Let $T$ be the extended binary tree in (11), and let each circular node $v$ be assigned the value equal to the sum of the weights $w_j$ of all external nodes in the subtree rooted at $v$.
Exercise 9. [**] [M21] The numbers appearing in the circular nodes of (11) are equal to the sums of the numbers appearing in their external-node descendants. Show that the sum of the circular node values is equal to the weighted path length.
Verified: yes
Solve time: 57s
Let $T$ be the extended binary tree in (11), and let each circular node $v$ be assigned the value equal to the sum of the weights $w_j$ of all external nodes in the subtree rooted at $v$. Let $S(v)$ denote this value. The weighted path length is $\sum_j w_j l_j$, where $l_j$ is the number of edges from the root to external node $j$.
Each external node $j$ contributes its weight $w_j$ to $S(v)$ exactly for those circular nodes $v$ that lie on the path from the root to $j$, including the root and excluding no internal node above the leaf, since every such node has $j$ in its subtree while every circular node not on this path has a subtree disjoint from $j$. The number of circular nodes on the path from the root to external node $j$ equals $l_j$, since each step from the root to $j$ passes through exactly one circular node and contributes one edge to the path length.
Therefore, when the sum $\sum_v S(v)$ is expanded by distributing each $S(v)$ into the weights of its descendant external nodes, each term $w_j$ is counted once for every circular node on the root-to-$j$ path. Hence the total contribution of $w_j$ to $\sum_v S(v)$ is $w_j l_j$. Summing over all external nodes yields
$$ \sum_v S(v) = \sum_j w_j l_j. $$
This completes the proof.
∎