/***
 
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;
}