colinrmitchell.com

Blog

Breadth-first Tree Search in Haskell

Posted Tuesday, February 10th 2015 in Programming - Permalink

Let’s assume we have a tree structure, such that each node may have an arbitrary number of branches:

data TreeNode a = TreeNode
    { value :: a, children :: [TreeNode a] }
    deriving (Show, Eq)

A depth-first search means that we follow a line of branches until it ends, then backtrack to where we were and do it over again, until we finally hit all nodes in the tree. A breadth-first search means that we first look at all the child nodes of the current node, then the child nodes of those nodes, and so forth, until we hit all nodes in the tree.

Using the tree structure above, let us create an example, infinite tree, using the following function:

buildTree :: String -> TreeNode String
buildTree value' =
    TreeNode
    {
        value = value',
        children = [buildTree $ (++) value' $ show x | x <- [1..3]]
    }

This creates an infinite tree, with each node containing three child nodes. Each node has a value that represents its position in the tree. The root node will be blank, and each child of that will have the values “1”, “2”, and “3”. The children of “1” will have values “11”, “12”, “13”, and the children of “11” will be “111”, “112”, “113”, and so on.

A depth-first search is performed by taking the value of the current node, and adding to that the value of each of it’s child nodes. Using the map function in Haskell, this always searches the children from first to last, giving a depth-first search:

depthFirstSearch :: TreeNode a -> [a]
depthFirstSearch tree =
   [value tree] ++ (concat $ map depthFirstSearch $ children tree)

A breadth-first search requires taking the value of the current node, and then taking the values of all children first, before looking at the children of the children:

breadthFirstSearch :: [TreeNode a] -> [a]
breadthFirstSearch tree =
    (map value tree) ++ (breadthFirstSearch $ concat $ map children tree)

Here is an example of the node values for each search type. We only take the first 50 values returned from each function.

Depth-first:

1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111111
111111111111111111111111
1111111111111111111111111
11111111111111111111111111
111111111111111111111111111
1111111111111111111111111111
11111111111111111111111111111
111111111111111111111111111111
1111111111111111111111111111111
11111111111111111111111111111111
111111111111111111111111111111111
1111111111111111111111111111111111
11111111111111111111111111111111111
111111111111111111111111111111111111
1111111111111111111111111111111111111
11111111111111111111111111111111111111
111111111111111111111111111111111111111
1111111111111111111111111111111111111111
11111111111111111111111111111111111111111
111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111

Breadth-first:

1
2
3
11
12
13
21
22
23
31
32
33
111
112
113
121
122
123
131
132
133
211
212
213
221
222
223
231
232
233
311
312
313
321
322
323
331
332
333
1111
1112
1113
1121
1122
1123
1131
1132
1133
1211

You can find the source code of a working example at my WebSVN site.


List Posts Newest Posts Page 1Next Page