TAOCP 2.3 Exercise 21

Section 2.3: Trees

Exercise 21. [**] [M22] If a tree has $n_1$ nodes of degree 1, $n_2$ nodes of degree 2, ..., and $n_m$ nodes of degree $m$, how many terminal nodes does it have?

Verified: no
Solve time: 38s

Let $N$ be the total number of nodes and let $t$ be the number of terminal nodes. Since the tree has $n_1$ nodes of degree $1$, $n_2$ nodes of degree $2$, ..., and $n_m$ nodes of degree $m$, we have

$$ N=t+n_1+n_2+\cdots+n_m. $$

Every node except the root has exactly one parent, hence the total number of edges is $N-1$. On the other hand, counting edges by degrees of nonterminal nodes, the total number of edges is

$$ n_1+2n_2+\cdots+mn_m. $$

Therefore

$$ n_1+2n_2+\cdots+mn_m=N-1. $$

Substituting for $N$ gives

$$ n_1+2n_2+\cdots+mn_m = t+n_1+n_2+\cdots+n_m-1, $$

so

$$ t = 1+\sum_{k=1}^m (k-1)n_k. $$

Hence the number of terminal nodes is

$$ \boxed{1+n_2+2n_3+\cdots+(m-1)n_m}. $$