#include<bits/stdc++.h>
using namespace std;
class Node{
public:
    int key;
    Node *leftChild;
    Node *rightChild;
    Node(int value)
    {
        key = value;
        leftChild = rightChild  = NULL;
    }
};

class Tree{
public:
    Node *root;
    Tree()
    {
        root = NULL;
    }
    void insertt(int value)
    {
        Node *newNode = new Node(value);

        if( root == NULL)
        {
            root = newNode;
            return;
        }
        else
        {
            Node *currentNode = root;
            Node *parrentNode = NULL;

            while(currentNode != NULL)
            {
                parrentNode = currentNode;
                if(value <= currentNode ->key)
                {
                    currentNode = currentNode -> leftChild;
                }
                else
                {
                    currentNode = currentNode -> rightChild;
                }
            }
            //newNode -> parent = parrentNode;
            if(value <= parrentNode -> key)
            {
                parrentNode -> leftChild = newNode;
            }
            else
            {
                parrentNode -> rightChild = newNode;
            }
        }
    }
    void printInorder(Node *temp)
    {
        if(temp != NULL)
        {
            printInorder( temp -> leftChild );
            cout<<temp->key<<" ";
            printInorder( temp -> rightChild);
        }
    }

    ///Search function without Recursion
//    void Search(Node *node,int value)
//    {
//        if( node == NULL)
//        {
//            cout<<"value is not found";
//            return;
//        }
//        while( node != NULL){
//            if( node-> key == value)
//            {
//                cout<<"value is "<<node->key<<" found";
//                return ;
//            }
//            if( value < node->key)
//                node = node->leftChild;
//            else
//                node = node->rightChild;
//        }
//        cout<<"Not found"<<endl;
//    }
    ///Search function with recusive
    Node * Search(Node *node,int value)
    {
        if( node == NULL)
        {
            //cout<<"value is not found";
            return node;
        }
        if( node-> key == value)
        {
            //cout<<"value is "<<node->key<<" found";
            return node;
        }
        if( value < node->key)
            Search( node->leftChild, value);
        else
            Search(node->rightChild , value);
    }
    int minimum( Node *node)
    {
        if( node->leftChild == NULL)
        {
            return node->key;
        }
        minimum( node->leftChild);
    }
    int maximum( Node *node )
    {
        if( node->rightChild == NULL)
        {
            //cout<<"Maximum Value is: " <<node->key<<endl;
            return node->key;
        }
        maximum( node->rightChild);
    }
    /// Successor hosce jar succssor ber korbo tar theke boro sob cheye choto number.
    /// key value tar right thakle right er sob ceye choto number ta successor.
    /// right child na thakle
    /// key ta kono parent er left child hole parent ta successor;
    /// key ta right child hole parent er parent ta successor.
    int  successor(Node *root,int value)
    {
        Node *temp = Search(root,value);
        if(temp == NULL)
        {
            return 0;
        }
        if( temp->rightChild != NULL)
            return minimum(temp->rightChild);

        else
        {
                Node *successor= NULL;
                Node *parent = root;
            while( temp->key != parent->key )
            {
                if( temp->key <= parent->key)
                {
                    successor = parent;
                    parent = parent->leftChild;
                }
                else
                    parent = parent->rightChild;
            }
            return successor->key;
        }
    }
    Node * deleteNode( Node *root, int value)
    {
        if( root == NULL)
        {
            return root;
        }
        else if( value < root->key)
            root->leftChild=deleteNode( root->leftChild, value);
        else if( value > root->key)
        {
            root->rightChild = deleteNode( root->rightChild, value);
        }
        else
        {
            /// No child
            if( root -> leftChild == NULL  &&  root->rightChild == NULL)
            {
                cout<<endl<<root->key<<endl;
                delete(root);
                root = NULL;
            }
            ///One Child
            else if( root -> leftChild == NULL)
            {
                Node *temp = root;
                root = root->rightChild;
                delete temp;
            }
            /// One child
            else if( root -> rightChild == NULL){
                Node *temp = root;
                root = root->leftChild;
                delete temp;
            }
            /// Two Child
            else
            {
                int succesor = minimum( root->rightChild);
                Node *temp = Search(root,succesor);
                root->key = temp -> key;
                root-> rightChild = deleteNode( root->rightChild, temp->key);
            }
        }
        return root;
    }

};

int main()
{
    Tree t;
    cout<<"How many value you want to insert: ";
    int n;
    cin>>n;
    while(n--)
    {
        int key;
        cin>>key;
        t.insertt(key);
    }
    t.printInorder(t.root);
    cout<<endl<<"which Value you want to search ";
    int value;
    cin>>value;


    Node *find = t.Search( t.root,value);
    if(find == NULL)
    {
        cout<<"Value is not found "<<endl;
    }
    else
    {
        cout<<find->key<<" is found "<<endl;
    }



    cout<<endl<<"Minimum Value is: "<<t.minimum(t.root)<<endl;
    cout<<endl<<"Maximum Value is: "<<t.maximum(t.root)<<endl;

    cout<<"which value successor you want to find: ";
    cin>>value;
    cout<<endl<<"Successor is: "<<t.successor(t.root, value );
    cout<<"which data you want to delete";
    cin>>value;
    t.deleteNode(t.root,value);
    cout<<endl;
    t.printInorder(t.root);
    return 0;
}
/// Tree Input 9 15 8 18 6 10 4 7 9 12