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 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.

    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
            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


  7. programmingpraxis said


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


Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: