#include<cstdio>
#include<queue>
using namespace std;
struct TNode{
    int value=-1;
    TNode *left=NULL;
    TNode *right=NULL;
};

void preOrder(TNode *root){
    if(root){
        printf("%d ",root->value);
        preOrder(root->left);
        preOrder(root->right);
    }
}

void inOrder(TNode *root){
    if(root){
        inOrder(root->left);
        printf("%d ",root->value);
        inOrder(root->right);
    }
}

void postOrder(TNode *root){
    if(root){
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ",root->value);
    }
}

void levelOrder(TNode *root){
    queue<TNode*> que;
    que.push(root);
    TNode *p;
    while(!que.empty()){
        p=que.front();
        printf("%d ",p->value);
        if(p->left!=NULL){
            que.push(p->left);
        }
        if(p->right!=NULL){
            que.push(p->right);
        }
        que.pop();
    }
}

void BSTInsert(int x,TNode *root){
    TNode *s=new TNode;
    s->value=x;
    TNode *temp;
    temp=root;
    int cnt=0;
    while(root){
        if(x>root->value){
            temp=root;
            root=root->right;
            cnt++;
        }
        else if(x<root->value){
            temp=root;
            root=root->left;
            cnt++;
        }
        else{
            return;
        }
    }
        printf("position:%d\n",temp->value);
        if(cnt==0){
            root=new TNode;
            root->value=x;
        }
        else{
            if(x>temp->value){
                temp->right=s;
            }
            else{
                temp->left=s;
            }
        }

}


int main(){
    TNode *first,*p,*s;
    first=new TNode;
    first->value=30;
    p=new TNode;
    p->value=15;
    first->left=p;
    p=new TNode;
    p->value=41;
    first->right=p;
    s=new TNode;
    s->value=33;
    p->left=s;
    s=new TNode;
    s->value=50;
    p->right=s;

    printf("before level:\n");
    levelOrder(first);
    printf("\n");
    printf("before preOrder:\n");
    preOrder(first);
    printf("\n");

    BSTInsert(35,first);
    printf("after level:\n");
    levelOrder(first);
    printf("\n");
    printf("after preOrder:\n");
    preOrder(first);
    printf("\n");


    return 0;
}