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

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

```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 == l
for l in ls)
for ls in izip_longest(*(leaves(tree)
for tree in trees), fillvalue=uniq))
```
4. Kanak Kshetri said

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