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>

D

This version is quite long because it tries to be reliable. The code contains contracts, unit tests, annotations, and so on. <lang d>import std.array: empty; import std.algorithm: equal;

// Replace with an efficient stack when available in Phobos. struct Stack(T) {

   private T[] data;

   public @property bool empty() const pure nothrow {
       return data.empty;
   }

   // Can't be const if T isn't a value or const.
   public @property T head() const pure nothrow
   in {
       assert(!data.empty);
   } body {
       return data[$ - 1];
   }

   public void push(T x) pure nothrow {
       data ~= x;
   }

   public void pop() pure nothrow
   in {
       assert(!data.empty);
   } body {
       data.length--;
   }

}

struct BinaryTreeNode(T) {

   T data;
   BinaryTreeNode* left, right;

   this(T x, BinaryTreeNode* l=null, BinaryTreeNode* r=null)
   pure nothrow {
       this.data = x;
       this.left = l;
       this.right = r;
   }

}

struct Fringe(T) {

   alias const(BinaryTreeNode!T)* BT;
   private Stack!BT stack;

   pure nothrow invariant() {
       assert(stack.empty || isLeaf(stack.head));
   }

   public this(BT t) pure nothrow {
       if (t != null) {
           stack.push(t);
           if (!isLeaf(t)) {
               // Here invariant() doesn't hold.
               // invariant() isn't called for private methods.
               nextLeaf();
           }
       }
   }

   public @property bool empty() const pure nothrow {
       return stack.empty;
   }

   public @property T front() const pure nothrow
   in {
       assert(!stack.empty && stack.head != null);
   } body {
       return stack.head.data;
   }

   public void popFront() pure nothrow
   in {
       assert(!stack.empty);
   } body {
       stack.pop();
       if (!empty())
           nextLeaf();
   }

   private static bool isLeaf(in BT t) pure nothrow {
       return t != null && t.left == null && t.right == null;
   }

   private void nextLeaf() pure nothrow
   in {
       assert(!stack.empty);
   } body {
       auto t = stack.head;

       while (!stack.empty && !isLeaf(t)) {
           stack.pop();
           if (t.right != null)
               stack.push(t.right);
           if (t.left != null)
               stack.push(t.left);
           t = stack.head;
       }
   }

}

bool sameFringe(T)(in BinaryTreeNode!T* t1, in BinaryTreeNode!T* t2) pure nothrow {

   return Fringe!T(t1).equal(Fringe!T(t2));

}

unittest {

   alias BinaryTreeNode!int N;

   static N* n(in int x, N* l=null, N* r=null) pure nothrow {
       return new N(x, l, r);
   }

   {
       N* t;
       assert(sameFringe(t, t));
   }

   {
       const t1 = n(10);
       const t2 = n(10);
       assert(sameFringe(t1, t2));
   }

   {
       const t1 = n(10);
       const t2 = n(20);
       assert(!sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20));
       const t2 = n(30, n(20));
       assert(sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20));
       const t2 = n(10, n(30));
       assert(!sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20), n(30));
       const t2 = n(5, n(20), n(30));
       assert(sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20), n(30));
       const t2 = n(5, n(20), n(35));
       assert(!sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20, n(30)));
       const t2 = n(1, n(2, n(30)));
       assert(sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20, n(30, n(40), n(50))));
       const t2 = n(1, n(2, n(3, n(40), n(50))));
       assert(sameFringe(t1, t2));
   }

   {
       const t1 = n(10, n(20, n(30, n(40), n(50))));
       const t2 = n(1, n(2, n(3, n(40), n(51))));
       assert(!sameFringe(t1, t2));
   }

}

void main() {

   import std.stdio;
   alias BinaryTreeNode!int N;

   static N* n(in int x, N* l=null, N* r=null) pure nothrow {
       return new N(x, l, r);
   }

   const t1 = n(10, n(20, n(30, n(40), n(50))));
   writeln("fringe(t1): ", Fringe!int(t1));

   const t2 = n(1, n(2, n(3, n(40), n(50))));
   writeln("fringe(t2): ", Fringe!int(t2));

   const t3 = n(1, n(2, n(3, n(40), n(51))));
   writeln("fringe(t3): ", Fringe!int(t3));

   writeln("sameFringe(t1, t2): ", sameFringe(t1, t2));
   writeln("sameFringe(t1, t3): ", sameFringe(t1, t3));

}</lang>

Output:

fringe(t1): [40, 50]
fringe(t2): [40, 50]
fringe(t3): [40, 51]
sameFringe(t1, t2): true
sameFringe(t1, t3): false

Haskell

<lang haskell>data Tree a = Nil | Node a (Tree a) (Tree a)

   deriving (Show, Eq)

fringe :: Tree a -> [a] fringe t = case t of

   Nil            -> []
   Node x Nil Nil -> [x]
   Node x n1 n2   -> (fringe n1) ++ (fringe n2)

sameFringe :: (Eq a) => Tree a -> Tree a -> Bool sameFringe t1 t2 = fringe t1 == fringe t2

main = do

   let t1 = Node 10 Nil (Node 20 (Node 30 (Node 40 Nil Nil) (Node 50 Nil Nil)) Nil)
   let t2 = Node 1 Nil (Node 2 (Node 3 (Node 40 Nil Nil) (Node 50 Nil Nil)) Nil)
   print $ sameFringe t1 t2

   let t3 = Node 1 Nil (Node 2 (Node 3 (Node 40 Nil Nil) (Node 51 Nil Nil)) Nil)
   print $ sameFringe t1 t3</lang>

Output:

True
False

J

<lang J> -:&([: ; <S:0)</lang>

Note that the time/space optimizations here can change with the language implementation.

TODO: add examples

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