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

Posted by programmingpraxis
Filed in Exercises
8 Comments »

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

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

  2. 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
  3. 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))
  4. 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))

  5. programmingpraxis said
    August 3, 2010 at 1:27 PM

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

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

  7. programmingpraxis said
    August 22, 2010 at 12:38 PM

    Carl,

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

    Phil

  8. Will Ness said
    September 4, 2023 at 5:35 PM

    Hi Phil, hope all is well. :)

    https://www.dreamsongs.com/10ideas.html contains John McCarthy’s (himself!) Common Lisp solution using the “gopher” function, which surgically rotates each tree in turn to the right until its left child is a leaf.

    Similarly, the Haskell solution above is problematic. The implied constraint in the problem is that the leaves enumeration be done in O(n) i.e. without any unnecessary overhead, but that flatten implementation will be quadratic for trees which are left-degenerate. Instead, and similar to the “gopher” idea, it should be defined as

        flatten t = go t []  where
        go (Leaf x) xs = [x] ++ xs
        go (Node lt rt) xs = go lt (go rt xs)

    which can be seen as doing the said rotations implicitly, if we squint hard enough, since just as a gopher it burrows down to the leftmost leaf first, thanks to Haskell’s lazy evaluation.

Leave a comment