= Full ternary tree
A <rooted tree> in which every internal <vertex> has exactly three <tree children>. For a finite <rooted tree> with $m$ <tree leaves> and internal <outdegrees> $d_v$, counting <edges> in two ways gives
$$
m=1+\sum_{v\text{ internal}}(d_v-1).
$$
Indeed, the number of <edges> is the total number of <vertices> minus one and also the sum of the internal <outdegrees>. Thus a full ternary tree with $N$ internal <vertices> has $m=1+2N$ <tree leaves>, always an <odd number>. More generally, if every internal <vertex> has either two or three <tree children>, $m=1+N_2+2N_3$. This <parity> controls the initial merge in <ternary Huffman coding>.
Back to article page
