// binary trees, 
// construction of search-trees (not necessarily balanced),
//   with insert methods.
// in-visit.

#include <stdio.h>
#include <iostream.h>

class btree{  // definition of the class of binary trees 
   int info;
   btree *l;
   btree *r;
public:
   btree(int n){ 
      info = n;
      l = NULL;
      r = NULL;  
   }
   btree(int n, btree *t1, btree *t2){
      info = n;
      l = t1;
      r = t2;
   } 
   ~btree(){ 
      if (!(l==NULL)) delete l;
      if (!(r==NULL)) delete r;
   }
   int root(){ return info; }
   btree* left_sub_bt(){ return l; }
   btree* right_sub_bt(){ return r; }   
   bool is_empty_left(){ return l==NULL; }
   bool is_empty_right(){ return r==NULL; }
   void insert_left(btree *t){
      if (!(l==NULL))
         cout << "error";
      else 
         l = t;
   }
   void insert_right(btree *t){
      if (!(r==NULL))
         cout << "error";
      else 
         r = t;
   }
};

// construction of a search tree from an array of integers

void insert_in_search_tree(btree *t,int k){
   if (k < t->root()){
      if (t->is_empty_left()) t->insert_left(new btree(k));
      else insert_in_search_tree(t->left_sub_bt(),k);
   }
   else {
      if (t->is_empty_right()) t->insert_right(new btree(k));
      else insert_in_search_tree(t->right_sub_bt(),k);
   }
}
      
btree* search_tree(int n, int *infos){
   if (n == 0) 
      return NULL;
   else {
      btree *t = new btree(infos[n-1]);
      for (n--; n>0 ; n--) insert_in_search_tree(t,infos[n-1]);
      return t;
   }
}

// in_visit of a binary tree

void in_visit(btree *t){
   if (!t->is_empty_left()) in_visit(t->left_sub_bt());
   printf("%d ", t->root(), " "); 
   if (!t->is_empty_right()) in_visit(t->right_sub_bt());
}
  
// main program
 
void main(int ac, char* av[]){
   int  i, tot;
   int  *ary;
   tot = ac - 1;
   ary = new int [tot];
   for(i=0; i<tot; i++)  sscanf( av[i+1], "%d", &(ary[i]) );
   btree *t;
   t = search_tree(tot,ary); 
   in_visit(t);
   delete t;
   delete ary;
   printf("\n");   
}