/* ================================================================

   Program to sort a sequence of positive integers termianted
   by a negative number. First a binary search sequence tree
   is constructed then the BSST is traversed in in-order fashion
   and the sorted list is printed.

   Also, saves the nodes in binary format on a file. Compile as
       gcc -ansi inpfile.c  -o objfile

   Prabu 3/15/94

   ================================================================ */
#define  NULL   '\0'
struct node
{
  int info;
  struct node *left;   /* left child */
  struct node *right;  /* right child */
};

const int nodesize = sizeof(struct node); /* in bytes */

insert(struct node *p, struct node **r)  /* insert node p in the tree */
{
  if (*r == NULL)
    *r = p;
  else
    if (p -> info < (*r)->info)
         insert(p, &(*r)->left);
    else insert(p, &(*r)->right);
  return;
}

inorder(struct node *r) /* print the integers in sorted form */
{
  if (r != NULL)
  {
    inorder(r->left);
    printf(" %d ", r->info);
    inorder(r->right);
  }
  return;
}

main()
{
  struct node *root, *p;
  int n;

  root = NULL;
  printf("Input sequence of integers & terminate by a negative value \n");
  scanf("%d", &n);
  while (n >= 0)
  {
    p = (struct node *) malloc(nodesize);    /* make a new node */
    p->info = n;
    p->left = p->right = NULL;
    insert(p, &root);
    scanf("%d", &n);
  }
  printf("\nSorted numbers are :\n");
  inorder(root);
  printf("\n");
}