= Solution
Measure the work of producing the entire output <list>, with constant-cost labels. Count height in levels, so a leaf has height one and $h=0$. A <perfect ternary tree> with $h+1$ levels has
$$
N_h=1+3+\cdots+3^h=\frac{3^{h+1}-1}{2}
$$
<vertices>. This is the <finite geometric series> formula, used without a new proof.
The three recursive calls cost $3T(h-1)$. Ordinary `concat = foldr (++) []` copies each immediate child result once, and each result has $N_{h-1}$ elements. Consequently the nonrecursive work is $\Theta(3N_{h-1}+1)=\Theta(3^h)$, giving
$$
T(0)=\Theta(1),\qquad T(h)=3T(h-1)+\Theta(3^h)\quad(h\geq1).
$$
Unroll this <recurrence relation>. At level $j$, the cost is $3^j\Theta(3^{h-j})=\Theta(3^h)$, and there are $h$ internal levels, followed by $3^h$ leaves. Therefore
$$
\boxed{T(\mathrm{flatten})(h)=\Theta((h+1)3^h)}.
$$
For $h\geq1$ this is conventionally written $\Theta(h3^h)$; in terms of total size it is $\Theta(N_h\log N_h)$. The extra height factor comes from copying labels at successive ancestors, even under <lazy evaluation> when the whole output is demanded. Merely producing its first constructor is a different cost question. If height instead counts edges, the source's height $h+1$ means $h+2$ levels; shifting the index by one leaves the boxed asymptotic bound unchanged. Part (c)'s suffix-passing implementation avoids this repeated copying.
Back to article page
