// binary trees, 
// construction of search-trees (balanced),
// in-visit.

#include <stdio.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; }
};

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

btree* make_tree(int min, int max, int *infos){
   if (min == max) { 
      return new btree(infos[min]); 
   }
   else { 
      int m = (min + max)/2; 
      if (min == m) return new btree(infos[m], NULL, 
                                               make_tree(m+1,max,infos));
      else return new btree(infos[m], make_tree(min,m-1,infos),
                                      make_tree(m+1,max,infos));
   }
}

btree* search_tree(int n, int *infos){
//   quicksort(n,infos); // order the array (not implemented here)
   return make_tree(0,n-1, infos);
}

// 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");   
}