It’s surprising that DFS and BFS appear so often, so an example to illustrate both. The key for DFS is to maintain a stack to resume the search, while BFS feels more natural with the help of concatMap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
{-# LANGUAGE RecordWildCards #-}

data BTree = Leaf Int
           | BTree { left :: BTree, right :: BTree }
           deriving (Show)

dfs :: BTree -> [Int]
dfs tree = loop [] [tree]
  where
    loop acc [] = reverse acc
    loop acc ((Leaf v):rest) = loop (v:acc) rest
    loop acc (BTree{..}:rest) = loop acc (left:right:rest)

bfs :: BTree -> [Int]
bfs tree = loop [] [tree]
  where
    to_leaf (Leaf v) = [v]
    to_leaf _ = []
    to_subtree BTree{..} = [left, right]
    to_subtree _ = []

    loop acc [] = acc
    loop acc level = loop (acc ++ (concatMap to_leaf level))
                          (concatMap to_subtree level)

tree = BTree {
              left = BTree {
                            left = Leaf 1,
                            right = Leaf 10
                           },
              right = Leaf 3
             }
main = do
  print $ dfs tree
  print $ bfs tree

-- [1,10,3]
-- [3,1,10]