Same fringe

Same fringe is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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 (that is, you may not use parent pointers to avoid recursion).

C

With rudimentary coroutine support based on ucontext. I don't know if it will compile on anything other than GCC. <lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <ucontext.h>

typedef struct { ucontext_t this, that; int inuse; void *in, *out; } co_t;

1. define MAX_CO 16

co_t coroutines[MAX_CO];

int co_init(void (*func)(), void *data) { co_t *c = 0; int i; for (i = 0; i < MAX_CO; i++) { if (coroutines[i].inuse) continue; c = coroutines + i; break; }

if (!c) return -1; c->inuse = 1; c->in = data;

if (-1 == getcontext(&c->that)) return 0;

if (!c->that.uc_stack.ss_sp) { c->that.uc_stack.ss_sp = malloc(8192); c->that.uc_stack.ss_size = 8192; } c->that.uc_link = &c->this;

makecontext(&c->that, func, 1, i); return i; }

int co_call(int id) { if (coroutines[id].inuse) swapcontext(&coroutines[id].this, &coroutines[id].that); return coroutines[id].inuse; }

void co_end(int id) { coroutines[id].inuse = 0; }

void co_yield(int id, void *data) { coroutines[id].out = data; swapcontext(&coroutines[id].that, &coroutines[id].this); }

void *co_collect(int id) { if (!co_call(id)) return 0; return coroutines[id].out; }

// end of coroutine stuff

typedef struct node node; struct node { int v; node *left, *right; };

node *newnode(int v) { node *n = malloc(sizeof(node)); n->left = n->right = 0; n->v = v; return n; }

void insert(node **root, node *n) { if (!*root) *root = n; else if ((*root)->v > n->v) insert(&(*root)->left, n); else insert(&(*root)->right, n); }

void trav(int id) { void tree_trav(node *r) { if (r) { tree_trav(r->left); co_yield(id, r); tree_trav(r->right); } }

tree_trav(coroutines[id].in); co_end(id); }

int tree_eq(node *a, node *b) { int c1 = co_init(trav, a); int c2 = co_init(trav, b);

node *p, *q; do { p = co_collect(c1), q = co_collect(c2); } while (p && q && p->v == q->v);

if (!p && !q) return 1;

co_end(c1); co_end(c2); return 0; }

int main() { int x[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1 }; int y[] = { 2, 5, 7, 1, 9, 0, 6, 4, 8, 3, -1 }; int z[] = { 0, 1, 2, 3, 4, 5, 6, 8, 9, -1 };

node *t1 = 0, *t2 = 0, *t3 = 0;

void mktree(int *buf, node **root) { int i; for (i = 0; buf[i] >= 0; i++) insert(root, newnode(buf[i])); }

mktree(x, &t1); // ordered binary tree, result of traversing mktree(y, &t2); // should be independent of insertion, so t1 == t2 mktree(z, &t3);

printf("t1 == t2: %s\n", tree_eq(t1, t2) ? "yes" : "no"); printf("t1 == t3: %s\n", tree_eq(t1, t3) ? "yes" : "no");

return 0; }</lang>

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 solution visits lazily the two trees in lock step like in the Perl 6 example, and stops at the first miss-match. <lang python>try:

   from itertools import zip_longest as izip_longest # Python 3.x

except:

   from itertools import izip_longest                # Python 2.6+

def fringe(tree):

   """Yield tree members L-to-R depth first,
   as if stored in a binary tree"""
   for node1 in tree:
       if isinstance(node1, tuple):
           for node2 in fringe(node1):
               yield node2
       else:
           yield node1

def same_fringe(tree1, tree2):

   return all(node1 == node2 for node1, node2 in
              izip_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 same_fringe(a, a)
   assert same_fringe(a, b)
   assert same_fringe(a, c)

   assert not same_fringe(a, x)
   assert not same_fringe(a, y)
   assert not same_fringe(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