TAOCP 2.3.4.5 Exercise 7
**Solution.
Exercise 7. [**] [M21] What is the relation between the external and internal path length in a $t$-ary tree? See exercise 6; this should be a generalization of Eq. (3).
Verified: yes
Solve time: 4m09s
Solution.
Let $T$ be an extended $t$-ary tree. Let
$$ n=\text{number of internal nodes}, $$
$$ s=\text{number of external (square) nodes}, $$
$$ I=\sum_{\text{internal }v}\operatorname{depth}(v), $$
$$ E=\sum_{\text{external }w}\operatorname{depth}(w). $$
By Exercise 6,
$$ s=(t-1)n+1. $$
We shall derive the relation between $E$ and $I$.
Every node except the root is the child of a unique internal node. Therefore the sum of the depths of all nonroot nodes can be computed by summing over the children of each internal node.
If an internal node $v$ is at depth $d$, each of its $t$ children is at depth $d+1$. Hence the total contribution of the children of $v$ to the sum of depths of all nonroot nodes is
$$ t(d+1). $$
Summing over all internal nodes,
$$ I+E =\sum_{\text{internal }v} t(\operatorname{depth}(v)+1). $$
Since
$$ \sum_{\text{internal }v}\operatorname{depth}(v)=I, $$
and there are $n$ internal nodes,
$$ I+E=tI+tn. $$
Therefore
$$ E=(t-1)I+tn. $$
Using Exercise 6,
$$ tn=t\frac{s-1}{t-1}, $$
so an equivalent form is
$$ E=(t-1)I+\frac{t(s-1)}{t-1}. $$
The most natural generalization of Knuth's binary-tree formula is thus
$$ \boxed{E=(t-1)I+tn}. $$
For $t=2$ this becomes
$$ E=I+2n, $$
which is exactly Eq. (3). Hence the formula is the desired generalization. ∎