#include<stdio.h>
#include<stdlib.h>
#define NI NULL
??
struct node{
????int key;
????struct node *rig;
????struct node *lef;
????struct node *par;
};
??
typedef struct node * Node;
??
Node root;
??
void insert(int v){
????Node a=NI;
????Node b=root;
????Node c;
??
????c=malloc(sizeof(struct node));
????c->key=v;
????c->lef=NI;
????c->rig=NIL;
??
????while(b!=NI){
????????a=b;
??
????????if(c->key < b->key) b=b->lef;
????????else b=b->rig;
????}
??
????????c->par=a;
??
????????if(a==NI) root=c;
????????else if(c->key < a->key) a->lef=c;
????????else a->rig=c;
}
??
void inorder(Node u){
????if(u!=NI){
????????inorder(u->lef);
????????printf(" %d",u->key);
????????inorder(u->rig);
????}
}
void preorder(Node u){
????if(u!=NI){
????????printf(" %d",u->key);
????????preorder(u->lef);
????????preorder(u->rig);
????}
}
??
int main(){
????int k,i,x;
????char com[20];
??
????scanf("%d",&k);
??
????for(i=0;i<k;i++){
????????scanf("%s",com);
??
????if(com[0]=='i'){
????????scanf("%d",&x);
????????insert(x);
????}
????else if(com[0]=='p'){
????????inorder(root);
????????printf("\n");
????????preorder(root);
????????printf("\n");
????}
????}
????return 0;
}