= Perfect ternary tree
{title2=$N_h=(3^{h+1}-1)/2$}
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}^h3^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.
Back to article page
