TREE PROBLEMS - II

1. Given two trees, return true if they are
structurally identical.

int sameTree(struct node* a, struct node* b) {
  // 1. both empty -> true
  if (a==NULL && b==NULL) return(true);

  // 2. both non-empty -> compare them
  else if (a!=NULL && b!=NULL) {
    return(
      a->data == b->data &&
      sameTree(a->left, b->left) &&
      sameTree(a->right, b->right)
    );
  }
  // 3. one empty, one not -> false
  else return(false);
}

2. code to count number of leaves in the tree

void count_leaf(mynode *root)
{
   if(root!=NULL)
   {
      count_leaf(root->left);
      if(root->left == NULL && root->right==NULL)
      {
        // This is a leaf!
        count++;
      }
      count_leaf(root->right);
   }
}

3. code to create copy of tree

mynode *copy(mynode *root)
{
  mynode *temp;
  if(root==NULL)return(NULL);
  temp = (mynode *) malloc(sizeof(mynode));
  temp->value = root->value;
  temp->left  = copy(root->left);
  temp->right = copy(root->right);
  return(temp);
}

4. code to create mirror copy of tree

mynode *copy(mynode *root)
{
  mynode *temp;
  if(root==NULL)return(NULL);
  temp = (mynode *) malloc(sizeof(mynode));
  temp->value = root->value;
  temp->left  = copy(root->right);
  temp->right = copy(root->left);
  return(temp);
}

5. Implementing level order traversal of a tree

If this is the tree,

        1
   2         3
5   6     7   8

its level order traversal would be

1 2 3 5 6 7 8


void levelOrderTraversal(mynode *root)
{
  mynode *queue[100] = {(mynode *)0}; // Important to initialize!
  int size = 0;
  int queue_pointer = 0;
  while(root)
  {
      printf("[%d] ", root->value);
      if(root->left)
      {
        queue[size++] = root->left;
      }
      if(root->right)
      {
        queue[size++] = root->right;
      }
      root = queue[queue_pointer++];   
  }
}