Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 1 / e / Solution

Emit the root subtree first, then the occurrences inside its children:

subs :: Tree a -> [Tree a]
subs t@(One _)   = [t]
subs t@(Two l r) = t : (subs l ++ subs r)

This is a preorder traversal of subtree occurrences. Equal-valued occurrences are retained: the answer is a list, not a deduplicated set. Every occurrence is either the root or lies in exactly one child, which proves completeness by structural induction.