= Solution
The direct <tree fold> for an inorder traversal is
``
flattenFold :: Tree a -> [a]
flattenFold = foldTree (\ls x rs -> ls ++ (x:rs)) []
``
By <structural induction>, the child lists are ascending; the <binary search tree> property places every left value below the root and every right value above it. The displayed <list concatenation> therefore gives an ascending list containing every stored value exactly once.
For a version with linear <time complexity> on every tree shape, use an accumulator:
``
flatten :: Tree a -> [a]
flatten t = onto t []
where
onto Empty zs = zs
onto (Tree l x r) zs = onto l (x : onto r zs)
``
This also has a higher-order <tree fold> expression using <difference lists>:
``
flattenLinear :: Tree a -> [a]
flattenLinear t =
foldTree (\l x r -> l . (x:) . r) id t []
``
Its folded value is a function that prepends the inorder traversal to a supplied tail. The accumulator invariant is `onto t zs = flattenFold t ++ zs`. Each node contributes one constructor, giving $\Theta(n)$ time to consume the output. By contrast, the direct list-valued fold can take $\Theta(n^2)$ on a left-skewed tree because `++` repeatedly copies left traversals.
Back to article page
