Book Image

Haskell Data Analysis Cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis Cookbook

By: Nishant Shukla

Overview of this book

Table of Contents (19 chapters)
Haskell Data Analysis Cookbook
Credits
About the Author
About the Reviewers
www.PacktPub.com
Preface
Index

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