## Carl Hewitt’s Same-Fringe Problem

### August 3, 2010

There are several ways to attack this problem. In some languages, you may want to use generators or iterators; one possibility in Scheme is to use continuations to capture the state of a scan through the tree, so that the computation can be resumed. However, the simplest approach is to use lazy lists (Scheme calls them streams), which are provided by a standard library called SRFI-41 Streams.

We begin by solving the problem the wrong way, flattening the two input trees to lists and comparing the lists for equality:

```(define (flatten tree)   (cond ((null? tree) '())         ((pair? (car tree))           (append (flatten (car tree))                   (flatten (cdr tree))))         (else (cons (car tree)                     (flatten (cdr tree))))))```

This `flatten` function is nearly the same as the one in the Standard Prelude. Then it is easy to test two trees for equality:

```(define (same-fringe? tree1 tree2)   (equal? (flatten tree1) (flatten tree2)))```

This works, but violates the terms of the problem. The solution is to use streams. Here is a stream version of `flatten`, which is identical to the `flatten` shown above except that it forms the tree into a stream instead of a list:

```(define-stream (flatten tree)   (cond ((null? tree) stream-null)         ((pair? (car tree))           (stream-append             (flatten (car tree))             (flatten (cdr tree))))         (else (stream-cons                 (car tree)                 (flatten (cdr tree))))))```

Then `same-fringe?` calls `stream-equal?` instead of `equal?` to compare the two streams, generating only as much of the stream as is necessary to determine if they are the same:

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

Here’s an example:

```> (same-fringe? = '(1 (2 3)) '((1 2) 3)) #t```

You can run the program at http://programmingpraxis.codepad.org/ZNuaLYqQ, which includes all the streams machinery from SRFI-41.

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