Same fringe

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.

Perl 6

Here we use pair notation for our "cons" cell, and the gather/take construct to traverse the leaves lazily. The === value equivalence is applied to the two lists in parallel via the Z ("zip") metaoperator. The all junctional predicate can theoretically short-circuit if any of its arguments are false, though current implementations tend to process in large enough batches that a strictly lazy solution is not guaranteed. <lang perl6>sub samefringe($a,$b) { all fringe($a) Z=== fringe($b) }

sub fringe ($tree) { gather fringeˊ($tree), take Any } multi fringeˊ (Pair $node) { fringeˊ $node.key; fringeˊ $node.value; } multi fringeˊ (Any $leaf) { take $leaf; }</lang> Testing: <lang perl6>my $a = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8; my $b = 1 => (( 2 => 3 ) => (4 => (5 => ((6 => 7) => 8)))); my $c = (((1 => 2) => 3) => 4) => 5 => 6 => 7 => 8;

my $x = 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9; my $y = 0 => 2 => 3 => 4 => 5 => 6 => 7 => 8; my $z = 1 => 2 => (4 => 3) => 5 => 6 => 7 => 8;

say so samefringe $a, $a; say so samefringe $a, $b; say so samefringe $a, $c;

say not samefringe $a, $x; say not samefringe $a, $y; say not samefringe $a, $z;</lang>

Output:

True
True
True
True
True
True

Python

This example traverses each tree in step like in the Perl 6 example and will stop at the first miss-match without necessarily completing tree traversals and comparisons. <lang python>try:

 from itertools import zip_longest

except:

 try:
   from itertools import izip_longest
 except:
   zip_longest = lambda *args: map(None, *args)

def fringe(tree):

   'Yield tree members L-to-R depth first, as if stored in a binary tree'
   for node in tree:
       if type(node) != tuple:
           yield node
       else:
           for nd in fringe(node): yield nd

def samefringe(tree1, tree2):

   return all(node1 == node2
              for node1, node2 in zip_longest(fringe(tree1), fringe(tree2)))

if __name__ == '__main__':

   a = 1, 2, 3, 4, 5, 6, 7, 8
   b = 1, (( 2, 3 ), (4, (5, ((6, 7), 8))))
   c = (((1, 2), 3), 4), 5, 6, 7, 8
    
   x = 1, 2, 3, 4, 5, 6, 7, 8, 9
   y = 0, 2, 3, 4, 5, 6, 7, 8
   z = 1, 2, (4, 3), 5, 6, 7, 8
   
   assert samefringe(a, a)
   assert samefringe(a, b)
   assert samefringe(a, c)

   assert not samefringe(a, x)
   assert not samefringe(a, y)
   assert not samefringe(a, z)</lang>

Output:

There is no output, which signifies success.

Tcl

Works with: Tcl version 8.6

Library: Tcllib (Package: struct::tree)

<lang tcl>package require Tcl 8.6 package require struct::tree

1. A wrapper round a coroutine for iterating over the leaves of a tree in order

proc leafiterator {tree} {

   coroutine coro[incr ::coroutines] apply {tree {

yield [info coroutine] $tree walk [$tree rootname] node { if {[$tree isleaf $node]} { yield $node } } yieldto break

   }} $tree

}

1. Compare two trees for equality of their leaf node names

proc samefringe {tree1 tree2} {

   set c1 [leafiterator $tree1]
   set c2 [leafiterator $tree2]
   try {

while 1 { if {[set l1 [$c1]] ne [set l2 [$c2]]} { puts "$l1 != $l2"; # Just so we can see where we failed return 0 } } return 1

   } finally {

rename $c1 {} rename $c2 {}

   }

}</lang> Demonstrating: <lang tcl># Make some trees to compare... struct::tree t1 deserialize {

   root {} {}
     a 0 {}
       d 3 {}
       e 3 {}
     b 0 {}
     c 0 {}

} struct::tree t2 deserialize {

   root {} {}
     a 0 {}
       d 3 {}
       e 3 {}
     b 0 {}
     cc 0 {}

}

1. Print the boolean result of doing the comparison

puts [samefringe t1 t2]</lang>

Output:

c != cc
0