#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>

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); 
  // Inserts an item, sets success to true iff the item added.
  void DeleteOldItem(int Key, bool& success); 
  // Deletes an item, sets success to true iff the item removed.
  
  
  bool isEmpty();
  // Returns true if Root is NULL, otherwise returns false.   
  bool isLeaf();
  // Returns true if Root is a leaf (ie is defined but has neith right nor left children);
  
  int getRootItem();
  // Returns the value at the root if defined; if the Root is NULL returns -1.
  
  void getLeftSubTree(BST& L);
  // Puts a copy of the left subtree into L.
  void getRightSubTree(BST& R);
  // Puts a copy of the right subtree into R.
  
  // Traversals.
  void PrintPreOrder();
  void PrintInOrder();
  void PrintPostOrder();
  
  void depthFirstPrint () ;
  void breadthFirstPrint () ;
  
  protected:
   
  void copyTree (ptrType TreePtr, ptrType& NewTreePtr ) const; 
  // Copies the subtree rooted at ptrType to NewTreePtr

  void InsertItem (ptrType & TreePtr, int NewItem, bool&  success); 
  // Inserts a new item (iteratively) in its correct BST position; success it true iff successful
  void itInsert(ptrType &TreePtr, int NewItem);
  
  void DeleteItem(ptrType& TreePtr, int Key, bool &success);
  // Deletes item Key, restroring the BST; success is set to true iff the node was removed.
  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
    
  
  // Other traversals
  void depthFirst(ptrType &t);
  void breadthFirst(ptrType &t);
 
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) {itInsert (Root, NewItem); success= true; } 

 void BST::itInsert(ptrType &TreePtr, int NewItem) {
   ptrType temp= TreePtr;
   if (TreePtr== NULL) {
     TreePtr= new treeNode;
     TreePtr-> item = NewItem;
     TreePtr-> LChildPtr = NULL;
     TreePtr-> RChildPtr= NULL;
   }
   
   else {
   
   bool success= false;
   while(!success) {
   if ((temp -> item) < NewItem ) {
        if  ((temp -> RChildPtr) == NULL ) { // .. insert here
            temp->RChildPtr = new treeNode;
            temp -> RChildPtr -> item = NewItem;
            temp-> RChildPtr -> LChildPtr = NULL;
            temp-> RChildPtr -> RChildPtr= NULL;
            success= true;
            }
          else temp= temp -> RChildPtr;  // otherwise go right  
           } 
        else {
            if  ((temp -> LChildPtr) == NULL ) {
              temp->LChildPtr = new treeNode;
              temp -> LChildPtr -> item = NewItem;
              temp-> LChildPtr -> LChildPtr = NULL;
              temp-> LChildPtr -> RChildPtr= NULL;
              success= true;
            }
            else temp= temp -> LChildPtr;   
           }     
       } 
    }      					   
}
  
   
 void BST::PrintPreOrder() { PreOrder(Root);}
 void BST::PrintInOrder() { InOrder(Root); } 
 void BST::PrintPostOrder() {PostOrder(Root);}
  
  
 void BST::DeleteOldItem(int Key, bool& success) {DeleteItem(Root, Key, 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::copyTree (ptrType TreePtr, ptrType& NewTreePtr ) const {
    // Preordertraversal first

   if ( TreePtr != NULL ) { // copy the head
      NewTreePtr= new treeNode;
      NewTreePtr-> item = TreePtr-> item;
      NewTreePtr -> LChildPtr= NULL;
      NewTreePtr -> RChildPtr= NULL;

      copyTree( TreePtr -> LChildPtr, NewTreePtr -> LChildPtr); // recurse to the subtrees
      copyTree( TreePtr -> RChildPtr, NewTreePtr -> RChildPtr); 
   }
   else NewTreePtr= NULL;
}

  bool BST::isEmpty() {return (Root == NULL);}
  
  bool BST::isLeaf() {
  	if(isEmpty()) return false;
  	else { return (Root->LChildPtr==NULL) && (Root->RChildPtr==NULL);	  
  	}
  }
  
  int BST::getRootItem() {
  	if (Root==NULL) return -1;
  	else return Root->item;
  }

  void BST::getLeftSubTree(BST& L) {
     if (Root!=NULL) { 
     copyTree(Root->LChildPtr, L.Root);
     }
     else {L.Root= NULL;}
  }
   
  void BST::getRightSubTree(BST& R) {
    if (Root!=NULL) { 
    copyTree(Root->RChildPtr, R.Root);
    }
    else {R.Root= NULL;}
  };
  


  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 <<  " ";
     }
  }   
     
 
void BST::depthFirstPrint() {
  depthFirst(Root);
}  

void BST::depthFirst(ptrType& t) {
    stack<ptrType> st;
    st.push(t);
    ptrType temp;
    while(!st.empty()) {
     temp= st.top();
     if (temp!= NULL) {
       cout << temp-> item << " "; 
       st.pop();
       st.push(temp->RChildPtr);
       st.push(temp->LChildPtr); 
     }
     else st.pop();   
    }
   cout << endl; 
  } 
  
void BST::breadthFirstPrint() {
  breadthFirst(Root);
}  
   
void BST::breadthFirst(ptrType& t) {
    queue<ptrType> st;
    st.push(t);
    ptrType temp;
    while(!st.empty()) {
     temp= st.front();
     if (temp!= NULL) {
       cout << temp-> item << " "; 
       st.pop();
       st.push(temp->LChildPtr); 
       st.push(temp->RChildPtr);
     }
     else st.pop();   
    }
   cout << endl; 
  } 
  
#include "nodes.cpp"  
    
int main () {

  BST myTree;
  bool s;

  // insert items in the tree
  myTree.InsertNewItem(5, s);
  myTree.InsertNewItem(3, s);
  myTree.InsertNewItem(6, s);
  myTree.InsertNewItem(2, s);
  myTree.InsertNewItem(4, s);
  myTree.InsertNewItem(9, s);
  myTree.InsertNewItem(8, s);

  // output the sum of the leaves.
  cout << sumLeaves(myTree) << endl;   
}