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.
[…] 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 […]
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):
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))Bug in your solution.
> (define (same-fringe? eql? tree1 tree2)
> (stream-equal? = (flatten tree1) (flatten tree1)))
should be
(stream-equal? = (flatten tree1) (flatten tree2))
Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.
You might be interested in the solution in scriptJ(TM) at
http://arxiv4.library.cornell.edu/abs/1008.2748v1
Cheers,
Carl
Carl,
Thanks for the link. And thanks for visiting my corner of the web.
Phil