= Solution
In executable <Haskell>, the <algebraic data type> declaration uses `data`, rather than the printed `type`. A <leaf of a rooted tree> contributes `False`; a fork contributes `True` followed by its left and right <subtrees> in that order.
``
data Tree = Leaf | Fork Tree Tree
preorder :: Tree -> [Bool]
preorder Leaf = [False]
preorder (Fork l r) = True : (preorder l ++ preorder r)
``
This is a <preorder traversal> of a <full binary tree>, including the <leaf of a rooted tree>[leaves]. <Structural induction> proves correctness: the <leaf of a rooted tree> case has precisely one output, and the fork case concatenates the correct <preorder traversals> of its two <subtrees> after its own marker.
An equivalent version avoids repeatedly copying the left <list> through <list concatenation>:
``
preorder t = walk t []
where
walk Leaf rest = False : rest
walk (Fork l r) rest = True : walk l (walk r rest)
``
Its strengthening is `walk t rest = preorder t ++ rest`. Each <vertex> constructs one <list> cell, so this version has linear <time complexity>. The concise result is
$$
\boxed{P(\mathrm{Leaf})=[\mathrm{False}],\quad P(\mathrm{Fork}(l,r))=[\mathrm{True}]\mathbin{+\!+}P(l)\mathbin{+\!+}P(r).}
$$
Back to article page
