Traversing a tree breadth-first

In a breadth-first search approach to traversing a tree, nodes are visited in the order of the depth of the tree. The root is visited, then its children, then each of their children, and so on and so forth. This process requires a greater space complexity than the depth-first traversal but comes in handy for optimizing search algorithms.

For example, imagine trying to find all relevant topics from a Wikipedia article. Traversing all the links within the article in a breadth-first fashion will help ensure the topics start out with relevance.

Getting ready

Examine the tree in the following diagram. A breadth-first traversal will start at the root node r, then continue to the next level, encountering n1 and n4, finally followed by n2 and n3.

How to do it...

1. We will be using an existing implementation of a rose tree from Data.Tree:

   import Data.Tree (rootLabel, subForest, Tree(..))
   import Data.List (tails)

2. Implement the breadth-first traversal of a tree:

   breadthFirst...