Carl Hewitt’s Same-Fringe Problem

August 3, 2010

Long ago, Carl Hewitt created the same-fringe problem as a demonstration of the simplest problem that requires concurrency to implement efficiently: Given two binary trees, determine if they have the same leaves in the same order, regardless of their internal structure. A solution that simply flattens both trees into lists and compares them element-by-element is unacceptable, as it requires space to store the intermediate lists and time to compute them even if a difference arises early in the computation.

Your task is to write a function that tests if two trees have the same fringe. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

7 Responses to “Carl Hewitt’s Same-Fringe Problem”

Programming Praxis – Carl Hewitt’s Same-Fringe Problem « Bonsai Code said
August 3, 2010 at 10:21 AM
[…] Praxis – Carl Hewitt’s Same-Fringe Problem By Remco Niemeijer In today’s Programming Praxis exercise we have to implement Carl Hewitt’s same-fringe algorithm, which […]

Remco Niemeijer said

August 3, 2010 at 10:21 AM

My Haskell solution (see http://bonsaicode.wordpress.com/2010/08/03/programming-praxis-carl-hewitt%E2%80%99s-same-fringe-problem/ for a version with comments):

data Tree a = Node (Tree a) (Tree a) | Leaf a

flatten :: Tree a -> [a]
flatten (Node l r) = flatten l ++ flatten r
flatten (Leaf x)   = [x]

sameFringe :: Eq a => Tree a -> Tree a -> Bool
sameFringe a b = flatten a == flatten b

kbob said

August 3, 2010 at 11:56 AM

Here’s a Python solution using generators. Just for grins, I implemented seqsamefringe, which compares an arbitrary number of trees. Because cons cell is not a primitive type in Python, I implemented that, too.

#!/usr/bin/python

from itertools import izip_longest   # requires Python 2.6


# Define a tree/node class.

class Node:
    def __init__(self, left, right):
        self.left = left
        self.right = right
    def __str__(self):
        return "(%s %s)" % (str(self.left), str(self.right))
        
def is_leaf(tree):
    return not isinstance(tree, Node)


###### samefringe ######

def samefringe(tree1, tree2):
    class uniq: pass                    # unique object
    g1 = leaves(tree1)
    g2 = leaves(tree2)
    return all(l1 == l2 for (l1, l2) in izip_longest(g1, g2, fillvalue=uniq))

def leaves(tree):
    if is_leaf(tree):
        yield tree
    else:
        for leaf in leaves(tree.left):
            yield leaf
        for leaf in leaves(tree.right):
            yield leaf


# Compare a sequence of trees' fringes.

def seqsamefringe(*trees):
    class uniq: pass
    return all(all(ls[0] == l
                   for l in ls)
               for ls in izip_longest(*(leaves(tree)
                                        for tree in trees), fillvalue=uniq))

Kanak Kshetri said
August 3, 2010 at 12:54 PM
Bug in your solution.

> (define (same-fringe? eql? tree1 tree2)
> (stream-equal? = (flatten tree1) (flatten tree1)))

should be
(stream-equal? = (flatten tree1) (flatten tree2))
programmingpraxis said
August 3, 2010 at 1:27 PM
Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.
Carl Hewitt said
August 21, 2010 at 8:58 PM
You might be interested in the solution in scriptJ(TM) at

http://arxiv4.library.cornell.edu/abs/1008.2748v1

Cheers,
Carl
programmingpraxis said
August 22, 2010 at 12:38 PM
Carl,

Thanks for the link. And thanks for visiting my corner of the web.

Phil

S	M	T	W	T	F	S
« Jul				Sep »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Programming Praxis