= Solution
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{\operatorname{flatten}(\operatorname{Node}\ l\ x\ r)=\operatorname{flatten}(l)\mathbin{+\!+}[x]\mathbin{+\!+}\operatorname{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.
Back to article page
