// bst.cpp
// binary search tree
// FB - 201101263 
#include<iostream>
#include<iomanip> //width()
using namespace std;
#define width_unit 5
 
class Tree
{
    private:
        class Node
        {
            public:
                int data;
                Node *left, *right;
                Node(int d=0) //constructor
                    :data(d), left(NULL), right(NULL) {}
        };
 
        Node *root;
        Node * trav(int, Node * &);
        void chop(Node * N);
        void copy(Node * N);
        void print(ostream &, Node *, int) const;
        void print(Node *, int) const;
 
    public:
        Tree(void); //constructor
        ~Tree(void); //destructor
        bool find(int);
        void insert(int);
        void remove(int);
        bool empty(void) const;
        Tree(const Tree &); //copy constructor
        const Tree & operator=(const Tree &); //assignment operator overload
        friend ostream & operator<<(ostream &, const Tree &);
};
 
 
Tree::Tree(void)
{
     root=NULL;
}
 
bool Tree::empty(void) const
{
     return !root;
}
 
Tree::Node * Tree::trav(int foo, Node * & par)
{
     Node * curr=root;
     par=NULL;
     while(curr && curr->data != foo)
     {
         par=curr;
         if(foo < curr->data)
             curr=curr->left;
         else
             curr=curr->right;
     }
     return curr;
}
 
bool Tree::find(int foo)
{
     Node * par=NULL;
     Node * curr=trav(foo, par);
     return curr;
}
 
void Tree::insert(int foo)
{
     Node * par=NULL;
     Node * curr=trav(foo,par);
     if(!curr) //no duplicates
     {
         curr= new Node(foo);
         if(!par)
             root=curr;
         else if(foo < par->data)
             par->left=curr;
         else
             par->right=curr;
     }
}
 
void Tree::remove(const int foo)
{
     Node * par=NULL; //parent is null by default
     Node * curr=trav(foo,par); //locate the node of the foo
     if(curr) //if it is not null then
     {
         if(curr->left && curr->right) //2 children case
         {
             Node * tmp=curr;
             par=curr;
             curr=curr->left;
             while(curr->right)
             {
                 par=curr;
                 curr=curr->right;
             }
             tmp->data=curr->data;
         }
 
         //1 or 0 child case
         Node *tmp=(curr->left ? curr->left : curr->right);
 
         if(!par)
             root=tmp;
         else if(par->data < curr->data)
                  par->right=tmp;
              else
                  par->left=tmp;
         delete curr;
     }
}
 
void Tree::chop(Node *N)
{
     if(N)
     {
         chop(N->left);
         chop(N->right);
         delete N;
     }
}
 
//destructor
Tree::~Tree(void)
{
     chop(root);
}

Tree::Tree(const Tree & T)
{
     root=NULL;
     copy(T.root);
}

void Tree::copy(Node * N)
{
     if(N)
     {
         insert(N->data);
         copy(N->left);
         copy(N->right);
     }
}

const Tree & Tree::operator=(const Tree & T)
{
     if(this != &T)
     {
          chop(root);
          root=NULL;
          copy(T.root);
     }
     return *this;
}
 
//the recursive tree output
void Tree::print(ostream & ost, Node * curr, int level) const
{
     if(curr) //if the current node is not null then
     {
         print(ost,curr->right,level+1); //try to go to right node
         //output the node data w/ respect to its level
         ost<<setw(level*width_unit)<<curr->data<<endl;
         print(ost,curr->left,level+1); //try to go to left node
     }
}
 
//the recursive tree print
void Tree::print(Node * curr, int level) const
{
     if(curr) //if the current node is not null then
     {
         print(curr->right,level+1); //try to go to right node
         //print the node data w/ respect to its level
         cout<<setw(level*width_unit)<<curr->data<<endl;
         print(curr->left,level+1); //try to go to left node
     }
}
 
ostream & operator<<(ostream &ost, const Tree &t)
{
     t.print(ost, t.root, 1);
     return ost;
}

//Test 
int main()
{
    Tree mytree;
    mytree.insert(5);
    mytree.insert(3);
    mytree.insert(2);
    mytree.insert(7);
    mytree.insert(0);
    mytree.insert(2);
    cout<<mytree<<endl<<endl;
    mytree.remove(0);
    cout<<mytree<<endl<<endl;
    mytree.remove(5);
    cout<<mytree<<endl<<endl;
    mytree.insert(9);
    mytree.insert(10);
    mytree.insert(4);
    cout<<mytree<<endl<<endl;
    mytree.remove(9);
    cout<<mytree<<endl<<endl;

    Tree mytree2=mytree; //calls the copy constructor, not the assignment
    cout<<mytree2<<endl<<endl;

    Tree mytree3;
    mytree3=mytree2; //calls the assignment operator overload
    cout<<mytree3<<endl<<endl;
 
return 0;
}