#include<iostream>
#include<string>
#include<vector>

using namespace std;

struct treeNode {
                 int item;
                 treeNode* LChildPtr;
                 treeNode* RChildPtr;
                 };

typedef treeNode* ptrType;

class BST
{
  public:
  // Constructors

  BST();  // Default constructor.
  
  void SetRootData (int newItem);  // puts newItem at the root, creating it if necessary;

  void InsertNewItem ( int newItem , bool& success);
  
  void DeleteOldItem(int delItem, bool& success);

  void PrintPreOrder();
  void PrintInOrder();
  void PrintPostOrder();
  
  
  protected:
   
  void InsertItem ( ptrType & TreePtr, int NewItem, bool&  success); 
  
  void DeleteItem(ptrType& TreePtr, int Key, bool &success);
  void DeleteNodeItem(ptrType& Ptr);
  void ProcessLeftmost (ptrType& Ptr, int& rep);
  
  void PreOrder(ptrType tp); // Prints the nodes in PrePrder
  void InOrder(ptrType tp); // Prints the nodes using InOrder
  void PostOrder(ptrType tp); // Prints the nodes using PostOrder
 
private :

   ptrType Root; // The top of the tree. 
   
};

 BST::BST(): Root(NULL){}
 
  void BST::SetRootData (int newItem) {
    if (Root == NULL)  {
      Root= new treeNode;
      Root -> item= newItem;
      Root-> LChildPtr= NULL;
      Root -> RChildPtr= NULL;
     }
     else Root-> item= newItem;
 }  

  void BST::InsertNewItem (int NewItem, bool&  success) { InsertItem (Root, NewItem, success); } 

  void BST::InsertItem ( ptrType &TreePtr, int NewItem, bool &success) {
    // Implement an recursive definition for inserting an item in the BST
    // Note that "ptrType &TreePtr" means that TreePtr may be changed.
    }


  void BST::PrintPreOrder() { PreOrder(Root);}
  void BST::PrintInOrder() { InOrder(Root); } 
  void BST::PrintPostOrder() {PostOrder(Root);}
  void BST::DeleteOldItem(int delItem, bool& success){
    DeleteItem(Root, delItem, success);
  }

  
  
  void BST::DeleteItem(ptrType& TreePtr, int Key, bool &success) {
     if (TreePtr == NULL) success= false;
     
     else if (Key == TreePtr-> item) {
       DeleteNodeItem(TreePtr);
       success= true; // successful delete...
     }
     
     else if (Key < TreePtr -> item) DeleteItem(TreePtr ->LChildPtr, Key, success);
        // search the left....
     else   DeleteItem(TreePtr ->RChildPtr, Key, success); 
     //... or search the right.  
  }

void BST::DeleteNodeItem(ptrType& Ptr) {
   ptrType DelPtr;
   int ReplacementItem;
   
    // test for leaf..
   if ( (Ptr -> LChildPtr == NULL) && (Ptr -> RChildPtr == NULL)) {
      delete Ptr; // .. just delete
      Ptr= NULL;
   }
   
   // .. test for no left child..
   else if (Ptr -> LChildPtr == NULL) {// .. move the right child up and 
     DelPtr= Ptr;
     Ptr= Ptr -> RChildPtr;
     DelPtr->RChildPtr= NULL;         // ... delete the node.
     delete DelPtr;  
   }
   
   // .. test for no right child..
   else if (Ptr -> RChildPtr == NULL) {// .. move the left child up and 
     DelPtr= Ptr;
     Ptr= Ptr -> LChildPtr;
     DelPtr->LChildPtr= NULL;         // ... delete the node.
     delete DelPtr;  
   }
   
   //... if none of the above, the node must have two children..
   else { //.. take the first right, and then go left all the way..
     ProcessLeftmost(Ptr-> RChildPtr, ReplacementItem); //.. get the replacement item
     Ptr->item= ReplacementItem;
   } 
 }

void BST::ProcessLeftmost (ptrType& Ptr, int& rep) {
  if (Ptr-> LChildPtr == NULL)
    {
      rep= Ptr-> item; // .. this is the one..
      ptrType DelPtr= Ptr;
      Ptr= Ptr->RChildPtr;// .. move the right subtree up
      delete DelPtr; // Get rid of old node.  
    }
  else ProcessLeftmost(Ptr-> LChildPtr, rep); // ... otherwise, keep going left.  
}


  void BST::PreOrder(ptrType tp) {
     if ( tp != NULL ) {
        cout << tp -> item << " ";
        PreOrder( tp -> LChildPtr);
        PreOrder(tp -> RChildPtr);
     }
  }
  void BST::InOrder(ptrType tp) {
 if ( tp != NULL ) {
        InOrder( tp -> LChildPtr);
        cout << tp -> item << " ";
        InOrder(tp -> RChildPtr);  
     }
 }

  void BST::PostOrder(ptrType tp) {
   if ( tp != NULL ) {
        PostOrder( tp -> LChildPtr);
        PostOrder(tp -> RChildPtr);  
        cout << tp -> item <<  " ";
     }
  }   
     

int main () {

BST myTree;
bool s;

 myTree.SetRootData(6);
 myTree.InsertNewItem(4, s);
 myTree.InsertNewItem(9, s);
 myTree.InsertNewItem(0, s);
 myTree.InsertNewItem(3, s);
 myTree.InsertNewItem(7, s);
 myTree.InsertNewItem(10, s);
 myTree.InsertNewItem(8, s);
 

 cout << "Here's a Pre-order traversal " << endl;
    myTree.PrintPreOrder();  

    cout << endl;

  cout << "Here's an In-order traversal " << endl;
     myTree.PrintInOrder();

    cout << endl;
  cout << "Here's a Post-order traversal " << endl;
    myTree.PrintPostOrder();
   cout << endl;
   
   cout << "Try removing item 6" << endl;
  myTree.DeleteOldItem(6, s);
   cout << "Here's an In-order traversal " << endl;
     myTree.PrintInOrder();
}