Reading material

Pages 205-212.

Additional material

(* trees, possibly of infinite depth *)
datatype 'a inf_tree = Leaf
                     | Branch of 'a * (unit -> ('a inf_tree list))

(* depth first traversal of a tree *)
fun depthFirst t =
  let fun dfs [] = Nil
        | dfs (Leaf :: ts) = dfs ts
        | dfs ((Branch(v, tsf)) :: ts) = Cons(v, fn() => dfs(tsf() @ ts))
  in dfs [t] end

(* breadth first traversal of a tree *)
fun breadthFirst t =
  let fun bfs [] = Nil
        | bfs (Leaf :: ts) = bfs ts
        | bfs ((Branch(v, tsf)) :: ts) = Cons(v, fn() => bfs(ts @ tsf()))
  in bfs [t] end