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 givesIndeed, 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.

A full ternary tree whose leaves all have the same depth. At depth $j$ there are $3^j$ vertices, so a tree with $h+1$ levels has $N_h={\sum }_{j=0}^h{3}^j=(3^{h+1}-1)/2$ vertices and $3^h$ leaves, by the finite geometric series formula. For a rose tree representation, recursively flattening children and joining their lists with ordinary list concatenation copies each label once per ancestor. The work is therefore $\Theta ((h+1)3^h)=\Theta (N_h\log N_h)$ when the complete output is demanded. Passing an already constructed suffix through the recursion instead emits each label once, giving $\Theta (N_h)$ work.