# Tree Traversal, Depth first and Breadth first in Haskell

Lately I’m really digging Functional Programming, and especially Haskell. I’ve been reading Real World Haskell, which is a very nice free book about Haskell.

Today I was wondering what Breadth First traversal was. Of course I should know this and it’s stupid I forgot. To make sure I wouldn’t forget in the future I made a little exercise to improve my Haskell skills, and to make sure I wouldn’t forget the Breadth First algorithm anymore.

Depth First and Breadth First are two different ways of traversing a tree. It is best illustrated by the following images from Wikipedia:

### Depth First

#### Pseudo (JS) code

Quite simple code

```
function DFS(G) {
return [G.value].concat(DFS(G.left), DFS(G.right))
}
```

### Breadth First

A bit more complicated code:

```
function BFS(G) {
queue = []
queue.push(G)
set = []
while (queue.length) {
t = queue.shift()
if (t.left) queue.push(t.left)
if (t.right) queue.push(t.right)
set.push(t.value)
}
return set
}
```

## Traversal in Haskell

First we have to define a data type for the Tree:

```
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
```

### Depth First

The Depth First traversal in Haskell is very easy. If you look at the pseudo code, we can almost directly translate that to Haskell.

```
traverseDF :: Tree a -> [a]
traverseDF Empty = []
traverseDF (Node a l r) = a : (traverseDF l) ++ (traverseDF r)
```

This is simply, concatenate the `a`

with the tree on the left and then on the
tree on the right, by recursively calling `traverseDF`

.

### Breadth First

Breadth First is more difficult. If you look at the pseudo code there is some queue, which we kind of have to replicate, to make sure that first the root node is added to the resulting set, then the nodes at the first level, second level and finally the leaves.

```
traverseBF :: Tree a -> [a]
traverseBF tree = tbf [tree]
where
tbf [] = []
tbf xs = map nodeValue xs ++ tbf (concat (map leftAndRightNodes xs))
nodeValue (Node a _ _) = a
leftAndRightNodes (Node _ Empty Empty) = []
leftAndRightNodes (Node _ Empty b) = [b]
leftAndRightNodes (Node _ a Empty) = [a]
leftAndRightNodes (Node _ a b) = [a,b]
```

At `tbf [tree]`

we add the root node to the queue list. Then with
`map nodeValue xs`

the values of the nodes of this level are added to the
resulting list. Then the `tbf`

function is called again with all the nodes of
the next level. The `leftAndRightNodes`

returns a list of the left and/or right
nodes of a node. These are concatenated with the other child nodes, and then
recursively called with `tbf`

, until all levels of the tree are traversed.

### It works!

So now we have two functions, `traverseDF`

and `traverseBF`

, so what are the
results. So lets define some tree first:

```
createTree = Node 'A'
(Node 'B'
(Node 'C' Empty Empty)
(Node 'D' Empty Empty)
)
(Node 'E'
(Node 'F' Empty Empty)
(Node 'G' Empty (Node 'H'
(Node 'I' Empty Empty)
Empty
))
)
```

And run this in GHCI:

```
> let x = createTree
> traverseDF x
"ABCDEFGHI"
> traverseBF x
"ABECDFGHI"
```

And indeed, these are the results we would expect!

## Conclusion

Now I won’t forget which algorithm is which, and I improved my Haskell skills a bit. Of course I did Google/StackOverflow for this problem a little, and should mention this blogpost, which basically the algorithm I used.