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:
Pseudo (JS) code
Quite simple code
A bit more complicated code:
Traversal in Haskell
First we have to define a data type for the Tree:
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
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.
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.
So now we have two functions,
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!
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.