#include <iostream>

template <class T>
class Tree{
private:
    struct TreeNode{
        T data;
        TreeNode *left;
        TreeNode *right;

        TreeNode(T val):data(val),left(NULL),right(NULL){}
        //~TreeNode(){
        //    delete left;
        //    delete right;
        //}
    };

    TreeNode *root;
    void printHelper(TreeNode *)const;
    void insertHelper(T data, TreeNode *leaf);
    void DeleteHelper(T data, TreeNode* &);
    void DeleteNode(TreeNode* &);
    bool searchElementHelper(T key, TreeNode *leaf);
    void copyTree(TreeNode *&thisRoot, TreeNode *rhsRoot);
    TreeNode* findSmallest(TreeNode *,TreeNode *&);
public:
    Tree();
    ~Tree();
    Tree(const Tree& rhs);
    const Tree& operator=(const Tree& rhs);
    void insert(T);
    void Delete(T);
    void print()const;
    bool searchElement(T _data);
};

template<class T>
Tree<T>::Tree():root(NULL){}

template<class T>
Tree<T>::Tree(const Tree& rhs){
    if(rhs.root==NULL)
        root=NULL;
    else
        copyTree(root,rhs.root);
}

template<class T>
void Tree<T>::copyTree(TreeNode *&thisRoot,TreeNode *rhsRoot){
    if(rhsRoot==NULL)
        thisRoot=NULL;
    else{
        thisRoot = new TreeNode(rhsRoot->data);
        copyTree(thisRoot->left,rhsRoot->left);
        copyTree(thisRoot->right,rhsRoot->right);
    }
}

template<class T>
const Tree<T>& Tree<T>::operator=(const Tree& rhs){
    if(this!=&rhs){
        copyTree(this->root,rhs.root);
    }
    return *this;
}

template<class T>
Tree<T>::~Tree(){
    delete root;
}

template<class T>
void Tree<T>::insert(T _data){
    if(root==NULL)
        root = new TreeNode(_data);
    else{
        insertHelper(_data, root);
    }
}

template<class T>
void Tree<T>::insertHelper(T data, TreeNode *leaf){
    if(data < leaf->data){
        if(leaf->left == NULL){
            TreeNode *newNode = new TreeNode(data);
            leaf->left = newNode;
        }else
            insertHelper(data,leaf->left);
    }else if(data > leaf->data){
        if(leaf->right==NULL){
            TreeNode *newNode = new TreeNode(data);
            leaf->right = newNode;
            return;
        }
        insertHelper(data,leaf->right);
    }else{
        std::cout << "The data already exist" << std::endl;
    }
}

template<class T>
void Tree<T>::Delete(T _data){
    if(root==NULL){
        std::cout <<"The Tree is emptyn";
        return;
    }
    DeleteHelper(_data,root);
}
template<class T>
void Tree<T>::DeleteHelper(T _data,TreeNode* &rootRef){
    if(rootRef==NULL)
        return;
    if(_data==rootRef->data)
        DeleteNode(rootRef);
    else if(_data < rootRef->data)
        DeleteHelper(_data,rootRef->left);
    else if(_data > rootRef->data)
        DeleteHelper(_data,rootRef->right);
}
template<class T>
void Tree<T>::DeleteNode(TreeNode* &rootRef){
    // The current node has no children
    TreeNode* temp = rootRef;
    if(rootRef->left==NULL && rootRef->right==NULL)
        rootRef = NULL;
    else if(rootRef->left==NULL && rootRef->right!=NULL)
        rootRef = rootRef->right;
    else if(rootRef->left!=NULL && rootRef->right==NULL)
        rootRef = rootRef->left;
    else{ //current node has two childreen
        //find the smallest element in the right subtree
        TreeNode* parent = rootRef;
        temp = rootRef->right;
        temp = findSmallest(temp,parent);
        rootRef->data = temp->data;
        if(parent==rootRef)
            parent->right = temp->right;
        else
            parent->left = temp->left;
    }
    delete temp;
}

template<class T>
typename Tree<T>::TreeNode* Tree<T>::findSmallest(TreeNode *root, TreeNode *&parent){
    if(root->left==nullptr)
        return root;
    std::cout << "ASda" << root->data << std::endl;
    return findSmallest(root->left,root);
}
template<class T>
void Tree<T>::print()const{
    if(root==NULL)
        std::cout << "The Tree has no element" << std::endl;
    else
        printHelper(root);
}

template<class T>
void Tree<T>::printHelper(TreeNode *root)const{
     if(root==NULL)
         return;
    printHelper(root->left);
    std::cout << root->data << " " << std::endl;
    printHelper(root->right);
}

template<class T>
bool Tree<T>::searchElement(T _data){
    return searchElementHelper(_data,root);
}

template<class T>
bool Tree<T>::searchElementHelper(T _data,TreeNode *rootRef){
    if(rootRef==NULL)
        return false;
    if(_data==rootRef->data)
        return true;
    if(_data < rootRef->data)
        return searchElementHelper(_data,rootRef->left);
    if(_data > rootRef->data)
        return searchElementHelper(_data,rootRef->right);
    return false;
}
int main(int argc, const char * argv[]) {
    Tree<int> tree;
    tree.insert(12);
    tree.insert(10);
    tree.insert(19);
    tree.insert(11);
    tree.insert(16);
    tree.insert(13);
    tree.insert(15);
    tree.insert(14);
    tree.Delete(16);
    if(tree.searchElement(16))
        std::cout << "Found" << std::endl;
    else
        std::cout << "NOT Found" << std::endl;
    tree.print();
    Tree<int> tree2 = tree;
    std::cout<<"The elements of Tree 2: n";
    tree2.print();

    Tree<int> tree3;
    tree3 = tree2;
    std::cout <<"The elements of Tree 3: n";
    tree3.print();
    return 0;
}