#include <stdio.h>

#define MAXN 100


int bst[MAXN][4];
int bstpnt,n,a,i,j,status;



int bstinsert(int key, int i)

{  if (bst[i][0] > key)
       {if (bst[i][2] == 0)
          { bst[i][2] = bstpnt;
            bst[bstpnt][0]= key;
            bst[bstpnt][1]= i;
            bst[bstpnt][2]= 0;
            bst[bstpnt][3]= 0;
            bstpnt++;
           }
         else
            bstinsert(key,bst[i][2]);
       }
     else
       {if (bst[i][3] == 0)
          { bst[i][3] = bstpnt;
            bst[bstpnt][0]= key;
            bst[bstpnt][1]= i;
            bst[bstpnt][2]= 0;
            bst[bstpnt][3]= 0;
            bstpnt++;
           }
          else
            bstinsert(key,bst[i][3]);
         }
   return(0);
}




int inordervisit(int m)
{
   if (bst[m][2] > 0)
      inordervisit(bst[m][2]);
   printf(" %d\n",bst[m][0]);
   if (bst[m][3] > 0)
      inordervisit(bst[m][3]);
   return(0);
}






int main ()

{
   bstpnt = 1;
   for (i=0 ; i < 4 ; i++ ) {bst[0][i]=0 ; bst[1][i]=0;}

   status = 1;
   while (status > 0)
   {
    printf("which operation? ");
    scanf("%d",&status);
    if (status == 1)
        {scanf("%d",&a);
         bstinsert(a,1);
        }
    else if (status == 2)
        {inordervisit(1);
        }
    else if (status == 3)
        {for (i=1 ; i < bstpnt ; i++ )
            {printf(" %d  -> ",i);
             for (j=0 ; j < 4 ; j++ )
                  {printf("  %d",bst[i][j]);
                   }
              printf("\n");
            }
         }

   }

    return(0);
}