#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

struct node
{ char * data;
  struct node * left, * right; };

struct node * create_node(const char * s)
{ struct node * n = (struct node *)malloc(sizeof(struct node));
  n->data = strdup(s);
  n->left = NULL;
  n->right = NULL;
  return n; }

void add_to_tree(struct node * * pp, const char * s)
{ if (* pp == NULL)
  { * pp = create_node(s);
    return; }
  int c = strcmp(s, (* pp)->data);
  if (c == 0)
    return;
  if (c < 0)
    add_to_tree(& (* pp)->left, s);
  else
    add_to_tree(& (* pp)->right, s); }

void print_tree(struct node * p, int depth)
{ if (p == NULL)
  { }
  else
  { print_tree(p->left, depth + 1);
    printf("%*s%s\n", depth*3+3, "", p->data);
    print_tree(p->right, depth + 1); } }

void output_tree(struct node * p, FILE * f)
{ if (p == NULL)
  { }
  else
  { output_tree(p->left, f);
    fprintf(f, "%s\n", p->data);
    output_tree(p->right, f); } }

void destroy_tree(struct node * p)
{ if (p == NULL)
    return;
  destroy_tree(p->left);
  destroy_tree(p->right);
  free(p->data);
  free(p); }

char * random_string(void)
{ int length = random() % 7 + 3;
  char * s = malloc(length + 1);
  int i;
  for (i = 0; i < length; i += 1)
    s[i] = random() % 26 + 'a';
  s[length] = 0;
  return s; }

void print(const char * s, int len)
{ putchar('\'');
  int i;
  for (i = 0; i < len; i += 1)
  { char c = s[i];
    if (c >= ' ' && c <= '~')
      putchar(c);
    else
      printf("[%d]", c); }
  putchar('\''); }

int main(int argc, char * argv[])
{ int size = atoi(argv[1]);
  char * * orig = (char * *)malloc(size * sizeof(char *));
  char * * copy = (char * *)malloc(size * sizeof(char *));
  int i;
  for (i = 0; i < size; i += 1)
    copy[i] = orig[i] = random_string();
  for (i = 0; i < size * 10; i += 1)
  { int a = random() % size, b = random() % size;
    char * temp = copy[a];
    copy[a] = copy[b];
    copy[b] = temp; }
  struct node * t1 = NULL, * t2 = NULL;
  for (i = 0; i < size; i += 1)
  { add_to_tree(& t1, orig[i]);
    add_to_tree(& t2, copy[i]); }
  printf("Tree 1\n");
  print_tree(t1, 0);
  printf("Tree 2\n");
  print_tree(t2, 0);
  int p1[2];
  pipe(p1);
  int p = fork();
  if (p == 0)
  { close(p1[0]);
    FILE * f = fdopen(p1[1], "w");
    output_tree(t1, f);
    exit(0); }
  close(p1[1]);
  int p2[2];
  pipe(p2);
  p = fork();
  if (p == 0)
  { close(p2[0]);
    FILE * f = fdopen(p2[1], "w");
    output_tree(t2, f);
    exit(0); }
  close(p2[1]);
  p = fork();
  if (p == 0)
  { FILE * f1 = fdopen(p1[0], "r");
    FILE * f2 = fdopen(p2[0], "r");
    int ended1 = 0, ended2 = 0, different = 0;
    while (1)
    { char s1[16], s2[16];
      char * t1 = fgets(s1, 16, f1);
      char * t2 = fgets(s2, 16, f2);
      if (t1 == NULL)
        ended1 = 1;
      if (t2 == NULL)
        ended2 = 1;
      if (strcmp(s1, s2) != 0)
      { different = 1;
        break; }
      if (ended1 && ended2)
        break;
      if (ended1 || ended2)
      { different = 1;
        break; } }
    if (different)
      printf("The trees were different\n");
    else
      printf("The trees were the same\n"); }
  int s;
  p = wait(& s);
  p = wait(& s);
  p = wait(& s); }