# 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 source: wikipedia.org

#### Pseudo (JS) code

Quite simple code source: wikipedia.org

A bit more complicated code:

## Traversal in Haskell

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

### 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.

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 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.

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:

And run this in GHCI:

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.