#include <iostream>
        #include <cstdlib>
        #include <cstdio>
        using namespace std;
        class BinarySearchTree
        {
        private:
            struct TreeNode
            {
                int key;
                TreeNode* left;
                TreeNode* right;
            };
            TreeNode* root; //root pointer

        public:
            void insert(int value)
            {
                 TreeNode* leaf_node;
                 TreeNode* t,*curr_node;
                 t->key = value;
                 t->right = NULL;
                 t->left = NULL;

                 if(root == NULL)
                 {
                     root  = t; //t is root now
                 }
                 else
                 {

                     curr_node = root;

                     while(curr_node != NULL)
                     {

                            leaf_node = curr_node;
                            if(value > curr_node ->key)
                            {
                                curr_node = curr_node->right;
                            }
                            else
                            {
                                curr_node = curr_node->left;
                            }
                     }
                    if(value > leaf_node ->key)
                    {
                        leaf_node->right = t;
                    }
                    else
                    {
                        leaf_node->left = t;
                    }

                 }
            }
            void remove(int value)
            {

                TreeNode* curr_node,*parent;
                if (root == NULL)
                {
                    cout<<"Tree is empty..!"<<endl;
                    return;
                }
                //We keep a variable called found
                int found = false;
                curr_node = root;
                while(curr_node != NULL)
                {
                    if(curr_node->key == value)
                    {
                        found = true;
                       break;
                    }

                    parent = curr_node;
                    if(value > curr_node->key)
                    {
                        curr_node = curr_node->right;
                    }
                    else
                    {
                        curr_node = curr_node ->left;
                    }
                }
                if(!found)
                {
                    cout<<"Value Not Found ..!"<<endl;
                    return;
                }
                if(curr_node->right == NULL && curr_node->left == NULL)
                {
                    if(parent->right == curr_node)
                    {
                        parent->right = NULL;
                        delete curr_node;
                    }
                    else
                    {
                        parent->left = NULL;
                        delete curr_node;
                    }
                    return;
                }

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

                TreeNode* check_node = curr_node->right;
                if(check_node->left == NULL)
                {

                    curr_node->key = check_node->key;
                    curr_node->right = check_node->right;
                    delete check_node;
                }
                else
                {
                    TreeNode* successor,*parent;
                    parent = check_node;
                    successor = check_node->left;
                    while(successor->left != NULL)
                    {
                        parent = successor;
                        successor = successor->left;
                    }
                    curr_node->key =  successor->key;
                    parent->left = successor->right;
                    delete successor;
                }
            }
            void inorder()
            {
                //recursive
                inorder(root);
            }
            void inorder(TreeNode* temp)
            {
                if(temp == NULL) return;
                inorder(temp->left);
                cout<<temp->key<<" ";
                 inorder(temp->right);
                cout<<temp->right<<" ";
            }
        };
        int main(int argc, char * argv[])
        {
            //Testing The Code
            BinarySearchTree t;
            t.insert(8);
            t.insert(3);
            t.insert(1);
            t.insert(5);
            t.insert(10);
            t.insert(9);
            t.insert(12);
            t.insert(11);
            //t.remove(22);
            //t.remove(11);
            //t.remove(12);
            //t.remove(10);

            return 0;
        }