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