= Solution
Let $n$ be the number of leaves; the total number of nodes is $2n-1$. <List concatenation> copies its left operand. For a <tree> whose left subtree contains $n-1$ leaves at each successive internal node, these copied lengths are $1,2,\ldots,n-1$. Their <sum> is $n(n-1)/2$, so the worst-case <running time> is \b[$\Theta(n^2)$].
A <difference list> representation avoids copying prefixes:
``
flattenFast :: Tree a -> [a]
flattenFast t = go t []
where
go (One x) acc = x:acc
go (Two l r) acc = go l (go r acc)
``
The <recursion invariant> is `go t acc = flatten t ++ acc`. The leaf case is immediate; the internal-node case uses <associativity> of <list concatenation>. Each node is visited once and each leaf contributes one output constructor, giving \b[$\Theta(n)$ <running time>] when the result is fully consumed. This is <linear flattening of a binary tree> and does not assume balance.
Back to article page
