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

typedef struct _node {
   int key;
   int size;
   struct _node *L, *R;
} node;

typedef node *bintree;

bintree buildtree0 ( int *prekeys, int *inkeys, int pi, int pj, int ii, int ij )
{
   bintree T;
   int rootkey, nl, k;

   if ((pi > pj) || (ii > ij)) return NULL;
   if (pj - pi != ij - ii) return NULL;
   rootkey = prekeys[pi];
   for (k=ii; k<=ij; ++k) if (inkeys[k] == rootkey) break;
   if (k > ij) return NULL;
   nl = k - ii;
   T = (bintree)malloc(sizeof(node));
   T -> key = rootkey;
   T -> L = buildtree0(prekeys, inkeys, pi+1, pi+nl, ii, ii+nl-1);
   T -> R = buildtree0(prekeys, inkeys, pi+nl+1, pj, ii+nl+1, ij);
   return T;
}

bintree buildtree1 ( int *inkeys, int *postkeys, int ii, int ij, int pi, int pj )
{
   bintree T;
   int rootkey, nl, k;

   if ((ii > ij) || (pi > pj)) return NULL;
   if (ij - ii != pj - pi) return NULL;

   rootkey = postkeys[pj];
   for (k=ii; k<=ij; ++k) if (inkeys[k] == rootkey) break;
   if (k > ij) return NULL;
   nl = k - ii;
   T = (bintree)malloc(sizeof(node));
   T -> key = rootkey;
   T -> L = buildtree1(inkeys, postkeys, ii, ii+nl-1, pi, pi+nl-1);
   T -> R = buildtree1(inkeys, postkeys, ii+nl+1, ij, pi+nl, pj-1);
   return T;
   return NULL;
}

bintree readtree ( char *fname, int set )
{
   bintree T;
   int n, i, *keys1, *keys2;
   FILE *fp;

   fp = (FILE *)fopen(fname, "r");
   if (fp == NULL) return NULL;
   fscanf(fp, "%d", &n);
   keys1 = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) fscanf(fp, "%d", keys1+i);
   keys2 = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) fscanf(fp, "%d", keys2+i);
   fclose(fp);

   if (set == 0) T = buildtree0(keys1,keys2,0,n-1,0,n-1);
   else T = buildtree1(keys1,keys2,0,n-1,0,n-1);

   free(keys1);
   free(keys2);

   return T;
}

void populatesizes ( bintree T )
{
   int nl, nr;

   if (T == NULL) return;
   nl = nr = 0;
   if (T -> L) {
      populatesizes(T -> L);
      nl = T -> L -> size;
   }
   if (T -> R) {
      populatesizes(T -> R);
      nr = T -> R -> size;
   }
   T -> size = 1 + nl + nr;
}

void writetreePC ( bintree T )
{
   if (T == NULL) return;
   printf("%d %d %d\n", T->key, (T->L) ? T->L->size : 0, (T->R) ? T->R->size : 0);
   writetreePC(T->L);
   writetreePC(T->R);
}

int main ()
{
   bintree T0, T1;

   printf("\n+++ Solving the even part\n");
   T0 = readtree("C0.txt",0);
   populatesizes(T0);
   printf("%d\n", T0->size);
   writetreePC(T0);

   printf("\n+++ Solving the odd part\n");
   T1 = readtree("C1.txt",1);
   populatesizes(T1);
   printf("%d\n", T1->size);
   writetreePC(T1);

   exit(0);
}