= Solution
Emit the root label, then concatenate the <depth-first traversals> of the child <rose trees> in order:
``
dft :: RTree a -> [a]
dft (Node x ts) = x : concatMap dft ts
``
This is <preorder traversal>:
$$
\boxed{\operatorname{dft}(\operatorname{Node}\ x\ [t_1,\ldots,t_k])=[x]\mathbin{++}\operatorname{dft}(t_1)\mathbin{++}\cdots\mathbin{++}\operatorname{dft}(t_k).}
$$
The <Haskell concatMap function> preserves child order and finishes each child subtree before moving to the next. A leaf yields its singleton label; the source example yields `[1,2,3,4,5,6,7]`.
Back to article page
