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.

About these ads

Pages: 1 2

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

  1. […] 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 […]

  2. Remco Niemeijer said

    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
    
  3. kbob said

    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))
    
  4. Kanak Kshetri said

    Bug in your solution.

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

    should be
    (stream-equal? = (flatten tree1) (flatten tree2))

  5. programmingpraxis said

    Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.

  6. You might be interested in the solution in scriptJ(TM) at

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

    Cheers,
    Carl

  7. programmingpraxis said

    Carl,

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

    Phil

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: