Same fringe

type 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree

type 'a fringe_iterator = 'a tree list

let rec collect stack t = match t with
  | Leaf -> stack
  | Branch (x, Leaf, Leaf) -> t::stack
  | Branch (x, left, Leaf) -> collect stack left
  | Branch (x, left, right) -> collect (right::stack) left

let fringe_iter tree =
  collect [] tree

let fringe_next = function
  | [] -> None, []
  | x::xs ->
      match x with
       | Branch (x, Leaf, Leaf) ->
           Some x, (match xs with [] -> [] | y::ys -> collect ys y)
       | _ -> failwith "bad iterator"

let same_fringe a b =
  let rec cmp aiter biter =
    match fringe_next aiter, fringe_next biter with
     | (None, _), (None, _) -> true
     | (Some x, aiter'), (Some y, biter') ->
         if x <> y then false else cmp aiter' biter'
     | _ -> false in
  cmp (fringe_iter a) (fringe_iter b)