Introduction

An N-ary tree is a tree where each node can have any number of children, so traversal functions are naturally recursive in Haskell. The cleanest way to write them is to define a recursive tree type and then express each traversal order in terms of the node value plus recursive work over the list of children.

Define the Tree Type Clearly

A simple N-ary tree definition is enough for most traversal problems.

data Tree a = Node a [Tree a]
  deriving (Show, Eq)

Each Node stores one value and a list of child trees. The list may be empty, which naturally represents a leaf node.

Example tree:

1sampleTree :: Tree Int
2sampleTree =
3  Node 1
4    [ Node 2 [Node 5 [], Node 6 []]
5    , Node 3 []
6    , Node 4 [Node 7 []]
7    ]

Once the type is defined this way, most traversals become short recursive functions.

Write Preorder Traversal

Preorder means "visit the current node, then visit each child subtree."

preorder :: Tree a -> [a]
preorder (Node value children) =
  value : concatMap preorder children

This reads almost like the definition of preorder itself:

• emit the current value
• recursively traverse each child
• concatenate the results

For sampleTree, preorder sampleTree returns [1,2,5,6,3,4,7].

Write Postorder Traversal

Postorder means "visit all children first, then visit the current node."

postorder :: Tree a -> [a]
postorder (Node value children) =
  concatMap postorder children ++ [value]

That small change in concatenation order completely changes the traversal result. On the sample tree, the output becomes [5,6,2,3,7,4,1].

This is a good example of how Haskell rewards direct translation of the traversal rule into code.

Breadth-First Traversal Needs a Queue

Depth-first traversals fit plain recursion naturally. Breadth-first traversal is easier if you model a queue explicitly. Data.Sequence works well for that.

1import qualified Data.Sequence as Seq
2import Data.Sequence (Seq((:<|)), (|>))
3
4bfs :: Tree a -> [a]
5bfs root = go (Seq.singleton root)
6  where
7    go :: Seq (Tree a) -> [a]
8    go Seq.Empty = []
9    go (Node value children :<| rest) =
10      value : go (foldl (|>) rest children)

Here the queue starts with the root node. Each step removes the front node, emits its value, and appends its children to the back. That produces level-order traversal.

For sampleTree, bfs sampleTree returns [1,2,3,4,5,6,7].

Generalize Traversal Thinking

Once you understand the recursive shape, many tree functions become small variations on the same theme:

• collecting values
• counting nodes
• searching for a match
• mapping a function over the tree

For example, counting nodes is just:

countNodes :: Tree a -> Int
countNodes (Node _ children) =
  1 + sum (map countNodes children)

That is useful because it reinforces the real pattern: solve the current node, then combine results from all child subtrees.

Prefer Clear Recursion Before Over-Abstraction

It is tempting to jump straight to folds, zippers, or type class abstractions. Those are powerful, but if the task is simply "write a traversal," the straightforward recursive version is usually the best first answer.

Once the traversal logic is correct and tested, you can refactor repeated patterns into folds or other reusable helpers. Writing the explicit version first keeps the control flow obvious and makes debugging much easier.

Common Pitfalls

• Defining the tree type in a way that makes leaf nodes awkward to represent.
• Mixing up preorder and postorder by placing the current value on the wrong side of the recursive call.
• Trying to write breadth-first traversal with plain recursion and no queue structure.
• Using repeated list append in the wrong place and accidentally making the traversal less efficient.
• Over-abstracting before the recursive structure of the traversal is fully understood.

Summary

• An N-ary tree in Haskell is naturally modeled as a value plus a list of child trees.
• Preorder and postorder are simple recursive functions built with concatMap.
• Breadth-first traversal is easier with an explicit queue such as Data.Sequence.
• Many other tree algorithms follow the same recursive shape.
• Write the direct recursive solution first, then generalize only if the code really benefits from it.