Problem Statement

Write a routine that will compare the leaves ("fringe") of two binary trees to determine whether they are the same list of leaves when visited left-to-right. The structure or balance of the trees does not matter; only the number, order, and value of the leaves is important. Any solution is allowed here, but many computer scientists will consider it inelegant to collect either fringe in its entirety before starting to collect the other one. In fact, this problem is usually proposed in various forums as a way to show off various forms of concurrency (tree-rotation algorithms have also been used to get around the need to collect one tree first). Thinking of it a slightly different way, an elegant solution is one that can perform the minimum amount of work to falsify the equivalence of the fringes when they differ somewhere in the middle, short-circuiting the unnecessary additional traversals and comparisons. Any representation of a binary tree is allowed, as long as the nodes are orderable, and only downward links are used (for example, you may not use parent or sibling pointers to avoid recursion).

Let's start with the solution:

type 'a btree = Leaf of 'a | BTree of ('a btree * 'a btree)

let rec next = function
  | [] -> None
  | h :: t -> match h with
    | Leaf x -> Some (x,t)
    | BTree(a,b) -> next (a::b::t)

let samefringe t1 t2 =
  let rec aux s1 s2 = match (next s1, next s2) with
    | None, None -> true
    | None, _ | _, None -> false
    | Some(a,b), Some(c,d) -> (a=c) && aux b d in
  aux [t1] [t2]

(* Test: *)
let () =
  let u = BTree(Leaf 1, BTree(Leaf 2, Leaf 3)) in
  let v = BTree(BTree(Leaf 1, Leaf 2), Leaf 3) in
  let w = BTree(BTree(Leaf 3, Leaf 2), Leaf 1) in
  let check a b =
    print_endline (if samefringe a b then "same" else "different") in
  check u v; check v u; check v w;