TAOCP 2.3.4.5 Exercise 6
Let $n$ be the number of circular (internal) nodes and $s$ the number of square (external) nodes in an extended $t$-ary tree.
Exercise 6. [**] [16] If a $t$-ary tree is extended in the same way as in (1), by including square terminal nodes, what is the relation between the number of square nodes and the number of circular nodes, corresponding to Eq. (2)?
Verified: yes
Solve time: 1m11s
Let $n$ be the number of circular (internal) nodes and $s$ the number of square (external) nodes in an extended $t$-ary tree. Since the underlying graph is a free tree, the total number of nodes is $n+s$, hence the number of edges is
$$ n+s-1. $$
On the other hand, each internal node has exactly $t$ children and each external node has none, so counting edges by children gives
$$ tn $$
edges. Therefore
$$ n+s-1=tn, $$
and solving for $s$ yields
$$ s=(t-1)n+1. $$
Thus the analogue of Eq. (2) for extended $t$-ary trees is
$$ \boxed{s=(t-1)n+1}. $$
For $t=2$ this reduces to $s=n+1$, which is Eq. (2).