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).

import random, sequtils, strutils
 
type Node = ref object
  value: int
  left, right: Node
 
 
proc add(tree: var Node; value: int) =
  ## Add a node to a tree (or subtree), insuring values are in increasing order.
  if tree.isNil:
    tree = Node(value: value)
  elif value <= tree.value:
    tree.left.add value
  else:
    tree.right.add value
 
 
proc newTree(list: varargs[int]): Node =
  ## Create a new tree with the given nodes.
  for value in list:
    result.add value
 
 
proc `$`(tree: Node): string =
  # Display a tree.
  if tree.isNil: return
  result = '(' & $tree.left & $tree.value & $tree.right & ')'
 
 
iterator nodes(tree: Node): Node =
  ## Yield the successive leaves of a tree.
  ## Iterators cannot be recursive, so we have to manage a stack.
  ## Note: with Nim 1.4 a bug prevents to use a closure iterator,
  ## so we use an inline iterator which is not optimal here.
 
  type
    Direction {.pure.} = enum Up, Down
    Item = (Node, Direction)
 
  var stack: seq[Item]
  stack.add (nil, Down) # Sentinel to avoid checking for empty stack.
 
  var node = tree
  var dir = Down
 
  while not node.isNil:
    if dir == Down and not node.left.isNil:
      # Process left subtree.
      stack.add (node, Up)
      node = node.left
    else:
      yield node
      # Process right subtree of pop an element form stack.
      (node, dir) = if node.right.isNil: stack.pop() else: (node.right, Down)
 
 
proc haveSameFringe(tree1, tree2: Node): bool =
  ## Return true if the trees have the same fringe.
  ## Check is done node by node and terminates as soon as
  ## a difference is encountered.
  let iter1 = iterator: Node = (for node in tree1.nodes: yield node)
  let iter2 = iterator: Node = (for node in tree2.nodes: yield node)
  while true:
    let node1 = iter1()
    let node2 = iter2()
    if iter1.finished and iter2.finished: return true # Both terminates at same round.
    if iter1.finished or iter2.finished: return false # One terminates  before the other.
    if node1.value != node2.value: return false
 
 
when isMainModule:
  randomize()
  var values = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 
  values.shuffle()
  let tree1 = newTree(values)
  echo "First tree:  ", tree1
 
  values.shuffle()
  let tree2 = newTree(values)
  echo "Second tree: ", tree2
 
  let s = if haveSameFringe(tree1, tree2): "have " else: "don’t have "
  echo "The trees ", s, "same fringe: ", toSeq(tree1.nodes()).mapIt(it.value).join(", ")