#include<iostream>
#include<cstdlib>
using namespace std;

class BinarySearchTree
{
    private:
        struct treeNode
        {
            treeNode* left;
            treeNode* right;
            int data;
        };
        treeNode* root;

    public:
        BinarySearchTree()
        {
            root=NULL;
        }

        bool isEmpty()
        const{ return root==NULL;}


        void printinorder();
        void inorder(treeNode*);
        void printpreorder();
        void preorder(treeNode*);
        void printpostorder();
        void postorder(treeNode*);
        void insert(int);
        void remove(int);
};


void BinarySearchTree::insert(int d)
{
    treeNode* t= new treeNode;
    treeNode*parent;
    t->data=d;
    t->left=NULL;
    t->right=NULL;
    parent=NULL;

    if(isEmpty())
        root=t;
    else
    {
        treeNode* curr;
        curr=root;
        while(curr)
        {
            parent=curr;
            if(t->data > curr->data)
                curr=curr->right;
            else
                curr=curr->left;
        }

        if(t->data<parent->data)
            parent->left=t;
        else
            parent->right=t;
    }
}

void BinarySearchTree::remove(int d)
{
    bool found=false;
    if(isEmpty())
    {
        cout << "Tree is empty!\n";
        return;
    }

    treeNode* curr;
    treeNode* parent;
    curr=root;

    while(curr!=NULL)
    {
        if(curr->data==d)
        {
            found=true;
            break;
        }
        else
        {
            parent=curr;
            if(d>curr->data)
                curr=curr->right;
            else
                curr=curr->left;
        }
    }
    if(!found)
    {
        cout << "Data not found!";
        return;
    }

    if((curr->left==NULL&&curr->right!=NULL)||(curr->left!=NULL && curr->right==NULL))
    {
        if(curr->left==NULL&&curr->right!=NULL)
        {
            if(parent->left==curr)
            {
                parent->left=curr->right;
                delete curr;
            }
            else
            {
                parent->right=curr->right;
                delete curr;
            }
        }
        else
        {
            if(parent->left==curr)
            {
                parent->left==curr->left;
                delete curr;
            }
            else
            {
                parent->right=curr->left;
                delete curr;
            }
        }
        return;
    }

    if(curr->left==NULL&&curr->right==NULL)
    {
        if(parent->left==curr)
            parent->left=NULL;
        else
            parent->right=NULL;
        delete curr;
        return;
    }

    if(curr->left!=NULL&&curr->right!=NULL)
    {
        treeNode* chkr;
        chkr=curr->right;
        if((chkr->left==NULL)&&(chkr->right==NULL))
        {
            curr=chkr;
            delete chkr;
            curr->right=NULL;
        }
        else
        {
            if((curr->right)->left!=NULL)
            {
                treeNode* lcurr;
                treeNode* lcurrp;
                lcurrp=curr->right;
                lcurr=(curr->right)->left;
                while(lcurr->left!=NULL)
                {
                    lcurrp=lcurr;
                    lcurr=lcurr->left;
                }
                curr->data=lcurr->data;
                delete lcurr;
                lcurrp->left=NULL;
            }
            else
            {
                treeNode* tmp;
                tmp=curr->right;
                curr->data=tmp->data;
                curr->right=tmp->right;
                delete tmp;
            }
        }
        return;
    }
}

void BinarySearchTree::printinorder()
{
    inorder(root);
}

void BinarySearchTree::inorder(treeNode* p)
{
    if(p!=NULL)
    {
        if(p->left) inorder(p->left);
        cout << " " << p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else
        return;
}

void BinarySearchTree::printpreorder()
{
    preorder(root);
}


void BinarySearchTree::preorder(treeNode* p)
{
    if(p!=NULL)
    {
        cout << " " << p->data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else
        return;
}

void BinarySearchTree::printpostorder()
{
    postorder(root);
}

void BinarySearchTree::postorder(treeNode* p)
{
    if(p!=NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout << " "<<p->data<<" ";
    }
    else
        return;
}

int main()
{
    BinarySearchTree b;
    int ch, tmp, tmp1;
    while(1)
    {
        cout <<"\n\n";
        cin >> ch;
        switch(ch)
        {
            case 1: cout<< "insert: ";
                    cin >>  tmp;
                    b.insert(tmp);
                    break;
            case 2: cout << endl;
                    cout << " In-order traversal " << endl;
                    b.printinorder();
                    break;
            case 3: cout << endl;
                    cout << " pre-order " << endl;
                    b.printpreorder();
                    break;
            case 4: cout << endl;
                    cout << " post-order " << endl;
                    b.printpostorder();
                    break;
            case 5: cout << "enter data to delete: ";
                    cin >> tmp1;
                    b.remove(tmp1);
                    break;
            case 6:
                    return 0;
        }
    }
}