(Un)Expected Symmetries

There is an obvious isomorphism between depth-first and breadth-first traversals: perform one, but keeping enough information to reconstruct the tree from the traversal; do so, and finally perform the other.

Of course this isomorphism is not constructive; and it doesn't sound like it would be the simplest one possible. One thing the usual presentations of the algorithms do is obscure the parallels between both traversal strategies. Let's recall the type of rose trees:

type 'a tree = L of 'a | N of 'a tree list

and at their DFS traversal:

let rec fold_dfs f e = function
| L x -> f e x
| N t -> List.fold_left (fold_dfs f) e t

The last case in fold_dfs is a left fold over the list t of children: first visit the first child, then proceed with the rest of the tree. This makes the function distinctly non-tail-recursive. We can use an explicit stack to manage the children pending of being visited:

let fold_dfs f e t =
  let rec fold e = function
  | []       -> e
  | L x :: s -> fold (f e x) s
  | N t :: s -> fold e (t @ s)
  in fold e [t]

Contrast this with the BFS traversal we've seen before:

let fold_bfs f e t =
  let rec fold e = function
  | []       -> e
  | L x :: q -> fold (f e x) q
  | N t :: q -> fold e (q @ t)
  in fold e [t]

The isomorphism couldn't be clearer.