The Same Fringe Problem

Richard Gabriel's "The Design of Parallel Programming Languages" writes: "The samefringe problem is this: two binary trees have the same fringe if they have exactly the same leaves reading from left to right."

The C2.com wiki suggests that the Same Fringe Problem is a "killer example of the utility of CoRoutines". There is a good discussion with implementations in a number of languages. The examples are generally recursive. This page has two examples in C which are not recursive and rely on "goto". The first assumes that each node in the tree does not have a pointer to its parent. This requires the code to remember how it found its way down the tree. The normal recursive technique relies on the stack. This code uses an array.

The second example relies on each node's parent pointer to find its way around the tree. In effect, the tree itself replaces the stack. This approach uses a small fixed number of bytes and it is fast. It can handle any tree it is given, regardless of depth, which is not true of recursive approaches. The code is more bulky, but not difficult to understand. Depending on one's requirements, it is a good solution to this type of problem. It is suggested that this problem does not so much call for coroutines or recursion as it does for our old friends C and goto.

This tarball has complete running code for both examples.

C implementation without parent pointers:

#include <stdio.h>
#include <stdlib.h>

#define PARENTS 1024

int compare(void *a, void *b);

struct node {
  struct node *left;
  struct node *right;
  void *content;
};

struct tree {
  struct node *root;
};

struct leaf_tracker {
  struct node *leaf;
  struct node *parents[PARENTS];
  int depth;
};

#define INC_DEPTH(depth)  \
  if(depth < PARENTS) { \
    depth++; \
  } \
  else { \
    fprintf(stderr, "The tree was too deep.\n"); \
    exit(1); \
  }

void next_leaf(struct tree *T, struct leaf_tracker *lt, int firstleaf)
{
  int i;

  if(firstleaf == 1) {
    for(i=0; i < PARENTS; i++)
      lt->parents[i] = NULL;

    if(T->root == NULL)
      goto all_done;

    lt->leaf = T->root;
    lt->depth = 0;

    goto just_arrived;
  }

 node_finished:
  if(lt->depth == 0) {
    goto all_done;
  }
  else if(lt->parents[lt->depth-1]->left == lt->leaf) {
    lt->leaf = lt->parents[--lt->depth];
    lt->parents[lt->depth] = NULL; /* Tidy */
    goto not_a_leaf;
  }
  else {
    lt->leaf = lt->parents[--lt->depth];
    lt->parents[lt->depth] = NULL; /* Tidy */
    goto node_finished;
  }

 not_a_leaf:
  if(lt->leaf->right != NULL) {
    lt->parents[lt->depth] = lt->leaf;
    INC_DEPTH(lt->depth);
    lt->leaf = lt->leaf->right;
    goto just_arrived;
  }
  else {
    goto node_finished;
  }

 just_arrived:
  if(lt->leaf->left != NULL) {
    lt->parents[lt->depth] = lt->leaf;
    INC_DEPTH(lt->depth);
    lt->leaf = lt->leaf->left;
    goto just_arrived;
  }
  else {
    goto maybe_leaf;
  }

 maybe_leaf:
  if(lt->leaf->right == NULL) {
    goto is_a_leaf;
  }
  else {
    lt->parents[lt->depth] = lt->leaf;
    INC_DEPTH(lt->depth);
    lt->leaf = lt->leaf->right;
    goto just_arrived;
  }

 is_a_leaf:
  return;

 all_done:
  lt->leaf = NULL;
  return;
}

int compare_fringes(struct tree *T1, struct tree *T2,
                    struct leaf_tracker *lt1, struct leaf_tracker *lt2)
{
  next_leaf(T1, lt1, 1);
  next_leaf(T2, lt2, 1);

 loop:
    if(lt1->leaf == NULL && lt2->leaf == NULL)
      return 1;
    else if(lt1->leaf == NULL)
      return 0;
    else if(lt2->leaf == NULL)
      return 0;
    else if(compare(lt1->leaf->content, lt2->leaf->content) != 0)
      return 0;

    next_leaf(T1, lt1, 0);
    next_leaf(T2, lt2, 0);

    goto loop;
}

C implementation with parent pointers:

#include <stdio.h>

int compare(void *a, void *b);

struct node {
  struct node *p;
  struct node *left;
  struct node *right;
  void *content;
};

struct tree {
  struct node *root;
};

struct leaf_tracker {
  struct node *leaf;
};

void next_leaf(struct tree *T, struct leaf_tracker *lt, int firstleaf)
{
  int i;

  if(firstleaf == 1) {
    if(T->root == NULL)
      goto all_done;

    lt->leaf = T->root;

    goto just_arrived;
  }

 node_finished:
  if(lt->leaf->p == NULL)
    goto all_done;
  else if(lt->leaf->p->left == lt->leaf) {
    lt->leaf = lt->leaf->p;
    goto not_a_leaf;
  }
  else {
    lt->leaf = lt->leaf->p;
    goto node_finished;
  }

 not_a_leaf:
  if(lt->leaf->right != NULL) {
    lt->leaf = lt->leaf->right;
    goto just_arrived;
  }
  else {
    goto node_finished;
  }

 just_arrived:
  if(lt->leaf->left != NULL) {
    lt->leaf = lt->leaf->left;
    goto just_arrived;
  }
  else {
    goto maybe_leaf;
  }

 maybe_leaf:
  if(lt->leaf->right == NULL) {
    goto is_a_leaf;
  }
  else {
    lt->leaf = lt->leaf->right;
    goto just_arrived;
  }

 is_a_leaf:
  return;

 all_done:
  lt->leaf = NULL;
  return;
}

int compare_fringes(struct tree *T1, struct tree *T2,
                    struct leaf_tracker *lt1, struct leaf_tracker *lt2)
{
  next_leaf(T1, lt1, 1);
  next_leaf(T2, lt2, 1);

 loop:
    if(lt1->leaf == NULL && lt2->leaf == NULL)
      return 1;
    else if(lt1->leaf == NULL)
      return 0;
    else if(lt2->leaf == NULL)
      return 0;
    else if(compare(lt1->leaf->content, lt2->leaf->content) != 0)
      return 0;

    next_leaf(T1, lt1, 0);
    next_leaf(T2, lt2, 0);

    goto loop;
}

Home     Software     Downloads     About