/* Problem 3--The Tree Movers
   This problem is naturally recursive.  In other words, if you let
   recursion do the work, it isn't that bad.  This solution actually
   builds the two trees, and then solves the problem:
   if the roots of the two trees differ, you have to wipe out A and copy
   in B.  If the roots are identical, you keep the root where it is, and
   recursively rebuild the left and right subtrees. */

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

typedef struct tree {
 int i;
 struct tree *l, *r;
} tree;

int main (int argc, char **argv);
int ReadTrees (FILE *in, tree **A, tree **B);
int ReadTree (FILE *in, tree **A);
void Add (tree **A, int val);
int count (tree *A);
int Process (tree *A, tree *B);
void Release (tree *A);

int main (int argc, char **argv) {

  FILE *in, *out;
  tree *A, *B;
  int cs, cmd, r;

 in = fopen ("prob3.in","r");
 out = fopen ("prob3.out","w");
 cs = 0;
 for (;;) {
 if (ReadTrees (in,&A,&B)) break;
  cmd = Process (A,B);
  if (cmd != 1) {
   fprintf (out,"Case %d: %d commands.\n",++cs,cmd);
  } else {
   fprintf (out,"Case %d: 1 command.\n",++cs);
  }
  Release (A);
  Release (B);
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* ReadTrees reads in trees A and B from in.  It returns true if there
   are no more trees to be read, false otherwise. */
int ReadTrees (FILE *in, tree **A, tree **B) {

  int r, sz;

 sz = ReadTree (in,A); /* read in the trees one at a time */
 if (sz==-1) {
  r = 1;
 } else {
  sz = ReadTree (in,B);
  r = 0;
 }
 return r;
}

/* ReadTree reads in tree A from in.  It returns the size of the tree.*/
int ReadTree (FILE *in, tree **A) {

  int sz, i, val;

 fscanf (in,"%d",&sz);
 *A = NULL;
 i = 0;
 for (;;) {
 if (i>=sz) break;
  fscanf (in,"%d",&val); /* Read in integer and add it to the tree */
  Add (A,val);
  i++;
 }
 return sz;
}

/* Add adds a value to a tree. */
void Add (tree **A, int val) {

 if (*A==NULL) { /* If tree is empty, the new node is the root. */
  *A = malloc (sizeof (tree));
  (*A)->i = val;
  (*A)->l = (*A)->r = NULL;
 } else {
  if (val < (*A)->i) {
   Add (&((*A)->l),val); /* Add new node to left subtree */
  } else {
   Add (&((*A)->r),val); /* Add new node to right subtree */
  }
 }
}

/* count returns the number of nodes in tree A. */
int count (tree *A) {

  int ct;

 if (A==NULL) { /* Base case */
  ct = 0;
 } else {
  ct = 1 + count (A->l) + count (A->r); /* Recursively count nodes */
 }
 return ct;
}

/* Process counts the number of commands needed to copy tree B into
   tree A */
int Process (tree *A, tree *B) {

  int cmd;

 if (A==NULL && B==NULL) { /* Two empty trees */
  cmd = 0;
 } else {
  if (B==NULL) { /* B empty, so just delete A */
   cmd = 1;
  } else {
   if (A==NULL) { /* A empty, so just copy B */
    cmd = count (B);
   } else {
    if (A->i != B->i) { /* need to delete A and copy B */
     cmd = 1+count (B);
    } else { /* recursively process subtrees */
     cmd = Process (A->l,B->l) + Process (A->r,B->r);
    }
   }
  }
 }
 return cmd;
}

/* Release frees up the memory used by tree A to prevent memory leaks */
void Release (tree *A) {

 if (A != NULL) {
  Release (A->l);
  Release (A->r);
  free (A);
 } else {
 }
}