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

/* #define DEBUG */
#if defined(DEBUG)
#include "xmalloc.h"
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
/* for xmalloc.c */
#define IDNODE 1001

struct NODE {
  int val;
  struct NODE *left;
  struct NODE *right;
};
 
void insert(struct NODE **root, int val) {
  if (*root == 0) {
    struct NODE *new_node = xmalloc(sizeof(struct NODE), IDNODE);
    new_node->val = val;
    new_node->left = new_node->right = 0;
    *root = new_node;
    return;
  }
  if (val < (*root)->val)
    insert(&((*root)->left), val);
  else
    insert(&((*root)->right), val);
}

void print(struct NODE **root) {
  if (*root) {
    if ((*root)->left)
      print(&((*root)->left));
    printf("%d ", (*root)->val);   
    if ((*root)->right)
      print(&((*root)->right));
    xfree(*root, IDNODE);
    *root = 0;
  }
}
 
#if 1
#define N 10
void insertValues(struct NODE **root, FILE *fp) {
  static char c[N];
  while (fgets(c, N, fp) != NULL)
    insert(root, atoi(c));
}
 
int main() {
  FILE *fp;  
  struct NODE *root = 0;
  if ((fp = fopen("numbers.txt", "r")) != 0) {
    insertValues(&root, fp);
    fclose(fp);
  }
  print(&root);
  return 0;
}
#else
#define SEED 31415926
#define N 1000
void check(struct NODE *root) {
  if (root) {
    if (root->left) {
      if (root->left->val > root->val) {
        printf("ERROR!!!\n");
        abort();
      }
      check(root->left);
    }
    if (root->right) {
      if (root->right->val < root->val) {
        printf("ERROR!!!\n");
        abort();
      }
      check(root->right);
    }
  }
}

int main() {
  int i;
  struct NODE *root = 0;  
  srand(SEED);
  for (i = 0; i < N; i++)
    insert(&root, rand() % N);  
  check(root);
  print(&root);
  fflush(0);
  xmallocdump();
  return 0;
}
#endif
/* end */