Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 2 / e / 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,\dots ,n-1$. Their sum is $n(n-1)/2$, so the worst-case running time is $\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 $\Theta (n)$ running time when the result is fully consumed. This is linear flattening of a binary tree and does not assume balance.