#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iomanip>
#include <string>
using namespace std;

int i = 0;


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

   public:
   BinarySearchTree()
   {
      root = NULL;
   }

   bool isEmpty() const { return root==NULL; }
   void print_inorder();
   void inorder(tree_node*);
   void print_preorder();
   void preorder(tree_node*);
   void print_postorder();
   void postorder(tree_node*,int);
   void insert(int);
   void remove(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
   tree_node* t = new tree_node;
   tree_node* parent;
   t->data = d;
   t->left = NULL;
   t->right = NULL;
   parent = NULL;

   // is this a new tree?
   if(isEmpty()) root = t;
   else
   {
      //Note: ALL insertions are as leaf nodes
      tree_node* curr;
      curr = root;
      // Find the Node's parent
      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)
{
   //Locate the element
   bool found = false;
   if(isEmpty())
   {
      cout<<" This Tree is empty! "<<endl;
      return;
   }

   tree_node* curr;
   tree_node* 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! "<<endl;
      return;
    }


    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    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->left;
            delete curr;
         }
       }
       return;
    }

    //We're looking at a leaf node
    if( curr->left == NULL && curr->right == NULL)
    {
      if(parent->left == curr)
      {
         parent->left = NULL;
      }
      else
      {
         parent->right = NULL;
      }
      delete curr;
      return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
       tree_node* chkr;
       chkr = curr->right;
       if((chkr->left == NULL) && (chkr->right == NULL))
       {
         curr = chkr;
         delete chkr;
         curr->right = NULL;
       }
       else // right child has children
       {
         //if the node's right child has a left child
         // Move all the way down left to locate smallest element

         if((curr->right)->left != NULL)
         {
            tree_node* lcurr;
            tree_node* 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
         {
            tree_node* tmp;
            tmp = curr->right;
            curr->data = tmp->data;
            curr->right = tmp->right;
            delete tmp;
         }

      }
      return;
   }

}
void BinarySearchTree::print_postorder()
{
   postorder(root,0);
}

void BinarySearchTree::postorder(tree_node* p, int indent=0)
{
    if(p != NULL) {
		if(p->right) postorder(p->right, indent+4);
		if(p==root) {
			cout<< p->data << "\n ";
			if(p->left) postorder(p->left, indent+4);
		}else{
			if(p->left) postorder(p->left, indent+4);

			if (indent) {
				std::cout << std::setw(indent) << ' ';
			}
			cout<< p->data << "\n ";
		}
    }
}

int main()
{
    BinarySearchTree b;
    int ch,tmp,tmp1;
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. Printing "<<endl;
       cout<<" 3. Removal "<<endl;
       cout<<" 4. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" Enter Number to be inserted : ";
                    cin>>tmp;
                    b.insert(tmp);
                    i++;
                    break;
           case 2 : cout<<endl;
                    cout<<" Printing "<<endl;
                    cout<<" --------------------"<<endl;
                    b.print_postorder();
                    break;
           case 3 : cout<<" Enter data to be deleted : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 4:
                    return 0;

       }
    }
}