/***

Bismillahir Rahmanir Rahim

 _______
|   __  \           _____
|  |__|  )_______   |   /     ____    ______
|   ____/ \__    \  |  |__   /    \  |      \
|  (        / __  \ |  __ \ /  __  \ |   /\  \
|  |       (____  / |     / \      / |__/  \  )
|__|            \/  |____/   \____/         \/


Sample Input

8

8 3 1 5 4 9 12 11

***/

#include <bits/stdc++.h>

using namespace std;

/* এটি আমাদের স্ট্রাকচার  */

struct BstNode
{
    int data;

    BstNode* left;

    BstNode* right;

};

/* মেমরিতে নতুন নোড নিচ্ছি  */

BstNode* GetNewNode(int data)
{
    BstNode* newNode = new BstNode();

    newNode->data = data;

    newNode->left = newNode->right = NULL;

    return newNode;
}

BstNode* Insert(BstNode* root, int data)
{
    if(root==NULL)
    {
        root = GetNewNode(data);
    }
    else if(data <= root->data)
    {
        root->left = Insert(root->left, data);
    }
    else
    {
        root->right = Insert(root->right, data);
    }
    return root;

}

BstNode* Search(BstNode* root, int key)
{
    if (root == NULL || root->data == key)
    {
        return root;
    }
    if (root->data < key)
    {
        return Search(root->right, key);
    }
    else
    {
        return Search(root->left, key);
    }
}

void printPreOrder(BstNode* root)
{
    if(root==NULL)
    {
        return;
    }

    printf("%d ", root->data);

    printPreOrder(root->left);

    printPreOrder(root->right);

}

void printInOrder(BstNode* root)
{
    if(root==NULL)
    {
        return;
    }

    printInOrder(root->left);

    printf("%d ", root->data);

    printInOrder(root->right);
}

void printPostOrder(BstNode* root)
{
    if(root==NULL)
    {
        return;
    }

    printPostOrder(root->left);

    printPostOrder(root->right);

    printf("%d ", root->data);
}

BstNode* maxValueNode(BstNode* node)
{
    BstNode* current = node;

    /* সবচেয়ে রাইটে যে আছে সেটিই সবচেয়ে বড়  */

    while (current->right != NULL)
        current = current->right;

    return current;
}

BstNode* deleteNode(BstNode* root, int key)
{
    /* বেস কেস  */

    if (root == NULL)
    {
        return root;
    }

    /* যে ডাটাটি ডিলিট করবো তা রুটের ভ্যালু থেকে ছোট হলে সেটি রুটের লেফট সাবট্রিতে আছে */

    if (key < root->data)
    {
        root->left = deleteNode(root->left, key);
    }

    /* যে ডাটাটি ডিলিট করবো তা রুটের ভ্যালু থেকে বড় হলে সেটি রুটের রাইট সাবট্রিতে আছে */

    else if (key > root->data)
    {
        root->right = deleteNode(root->right, key);
    }

    /* ডাটাটি রুটের ভ্যালুর সমান হলে এটিই সেই ডাটা যেটি আমরা ডিলিট করতে চাচ্ছি */

    else
    {
        /* নোডের যদি চাইল্ড না থাকে বা একটি চাইল্ড থাকে */

        if (root->left == NULL)
        {
            BstNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            BstNode* temp = root->left;
            free(root);
            return temp;
        }

        /* নোডের দুটি চাইল্ড থাকলে তার লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুকে আমরা খুঁজে বের করবো
           অথবা রাইট সাবট্রিয়ের সবচেয়ে ছোট ভ্যালুকে আমরা খুঁজে বের করবো
           এখানে আমরা লেফট সাবট্রিতে সার্চ দিয়েছি */

        BstNode* temp = maxValueNode(root->left);

        /* লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুই এখন আমাদের রুট হবে */

        root->data = temp->data;

        /* লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুটি যেহেতু আমাদের রুটে নিয়ে এসেছি
           তাই যেখান থেকে ভ্যালুটি এনেছি সেটিকে ডিলিট করে দেবো */

        root->left = deleteNode(root->left, temp->data);
    }

    return root;
}

int main()
{
    BstNode* root = NULL;

    int n, data,i,choice,val;

    printf("How many data's do you want to insert ?\n");

    scanf("%d", &n);

    for(i=1; i<=n; i++)
    {
        printf("Data %d: ", i);

        scanf("%d", &data);

        root = Insert(root, data);
    }

    printf("\nChoice 1 : Add a Node\n");
    printf("Choice 2 : Search a Node\n");
    printf("Choice 3 : Delete a Node\n");
    printf("Choice 4 : Traverse BST in Pre-Order\n");
    printf("Choice 5 : Traverse BST in In-Order\n");
    printf("Choice 6 : Traverse BST in Post-Order\n");

    puts("");

    printf("Enter your Choice : ");

    while(scanf("%d",&choice)==1)
    {
        if(choice==1)
        {
            printf("Enter a value to be added : ");

            scanf("%d",&val);

            root = Insert(root, val);
        }
        else if(choice==2)
        {
            printf("Enter a value to be Searched : ");

            scanf("%d",&val);

            if(Search(root,val)==NULL)
            {
                printf("The value doesn't exist in BST\n\n");
            }
            else
            {
                printf("The value exists in BST\n\n");
            }
        }
        else if(choice==3)
        {
            printf("Enter a value to be Deleted : ");

            scanf("%d",&val);

            deleteNode(root,val);
        }
        else if(choice==4)
        {
            printf("PreOrder Traversal: ");

            printPreOrder(root);

            printf("\n\n");
        }
        else if(choice==5)
        {
            printf("InOrder Traversal: ");

            printInOrder(root);

            printf("\n\n");
        }
        else if(choice==6)
        {
            printf("PostOrder Traversal: ");

            printPostOrder(root);

            printf("\n\n");
        }
        else
        {
            printf("Invalid Choice\n\n");
        }

        printf("Enter your Choice : ");
    }
    return 0;
}