Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / d

Use the empty list for an empty subtree, and join the left result, the current label and the right result:

flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []

Thus $\boxed{\mathrm{flatten}(\mathrm{Node}lxr)=\mathrm{flatten}(l)++[x]++\mathrm{flatten}(r)}$. This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below $x$ and every right label above $x$, proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.