/* This program repeatedly inserts n random numbers into
   a binary search tree. Then it traverse the tree
   in in-order to store the keys into array a.
   After the traversal, sorted numbers are in array a. */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define nil 0
int k=1;
struct item *proot;
struct item{
  int key;
  struct item *adr;
  struct item *left;
  struct item *right;
};
struct item a[1000000];
void insert(int x){
  struct item *p, *q;
  p=proot;
  do{
    q=p;
    if (x<=(*p).key)p=(*p).left; else p=(*p).right;
  }
  while (p!=nil);
  p=malloc(sizeof(struct item)); 
  (*p).key=x; (*p).left=nil; (*p).right=nil;
  (*p).adr=p;
  if (x<=(*q).key) (*q).left=p; else (*q).right=p;
}
traverse(struct item *proot)
{ struct item *p;
  p=proot;  
  if (p!=nil){
    printf("("); 
    traverse((*p).left);
    printf("%d", (*p).key);
    a[k]=(*p); k++;
    traverse((*p).right);
    printf(")"); 
  }
}
main()
{ 
  int i,n,t;
  scanf("%d",&n);
  proot=malloc(sizeof(struct item));
  (*proot).key=99999;
  (*proot).left=nil;
  (*proot).right=nil;
  for(i=1;i<=n;i++) a[i].key=random()%100000;
//  for (i=1;i<=n;i++)printf("%d ",a[i].key);
  printf("\n");
  t=clock();
  for (i=1;i<=n;i++)insert(a[i].key);
  traverse(proot->left);
  printf("\n");
  printf("time= %d millisec\n\n", (clock()-t)/1000);
/*
  for (i=1;i<=n;i++)
    printf("%3d %3d %3d %3d\n\n",(int)(a[i].adr) % 1000, a[i].key, 
                             (int)(a[i].left) % 1000, (int)(a[i].right) % 1000);
*/
}