template<class T>
class BinarySearchTree
{
public:
    template<class T>
    struct Node
    {
        T data;
        Node<T>* link_right;
        Node<T>* link_left;
    };
    typedef Node<T>* NodePtr;

private:
    NodePtr root;
    int m_size = 0;
public:
    //////////////////////////////////////////////////////////////////////
    //                          BinarySearchTree()                      //
    //////////////////////////////////////////////////////////////////////
    BinarySearchTree()
    {
        root = nullptr;
    }
    ~BinarySearchTree()
    {
        delete_post_order(root);
    }

    Node<T>* Getroot(){ return root; }

    //////////////////////////////////////////////////////////////////////
    //                          void insert()                           //
    //////////////////////////////////////////////////////////////////////
    void insert(T data)
    {
        Node<T>* temp = nullptr;//iterate
        Node<T>* inserter = nullptr;//set to correct position
        Node<T>* node = new Node<T>;//a new node, always a leaf
        node->data = data;
        node->link_left = nullptr;
        node->link_right = nullptr;
        if (root)
        {
            //no duplicate nodes in the BST
            temp = search(data);
            if (temp)
            {
                delete node;
            }
        }
        else
        {
            root = node;
            ++m_size;
            return;
        }
        temp = root;
        inserter = temp;
        while (temp)
        {
            //go all the way down the tree until a nullptr node is reached
            inserter = temp;
            if (data < temp->data)
            {
                temp = temp->link_left;
            }
            else if (data > temp->data)
            {
                temp = temp->link_right;
            }
        }
        //insert it at the correct place
        if (data < inserter->data)
        {
            inserter->link_left = node;
            ++m_size;
        }
        else
        {
            inserter->link_right = node;
            ++m_size;
        }
    }

    //////////////////////////////////////////////////////////////////////
    //                          void search()                           //
    //////////////////////////////////////////////////////////////////////

    Node<T>* search(T data)
    {
        //go through and return the node reference if found
        //else return null
        NodePtr iter = root;
        while (iter)
        {
            if (iter->data == data)
            {
                return iter;
            }
            else if (data < iter->data)
            {
                iter = iter->link_left;
            }
            else if (data > iter->data)
            {
                iter = iter->link_right;
            }
        }
        return nullptr;
    }


    //////////////////////////////////////////////////////////////////////
    //                          void erase()                            //
    //////////////////////////////////////////////////////////////////////

    void erase(T data)
    {
        Node<T>* iter = root;
        Node<T>* previous = nullptr;
        Node<T>* eraser = search(data);
        //verify eraser
        if (eraser)
        {
            //get the parent node for eraser
            while (iter)
            {
                previous = iter;
                if (eraser->data < iter->data)
                {
                    iter = iter->link_left;
                }
                else if (eraser->data > iter->data)
                {
                    iter = iter->link_right;
                }
                if (iter == eraser)
                {
                    break;
                }
            }

            //is eraser a leaf node?
            if (eraser->link_left == nullptr && eraser->link_right == nullptr)
            {
                RemoveLeaf(previous, eraser);
            }


            //does it have one child?
            else if (eraser->link_left == nullptr && eraser->link_right != nullptr)
            {
                RemoveWithOneChild(previous, eraser);
            }
            else if (eraser->link_right == nullptr && eraser->link_left != nullptr)
            {
                RemoveWithOneChild(previous, eraser);
            }

            //does it have two children? find the lowest right child node to replace
            else if (eraser->link_right && eraser->link_left)
            {
                RemoveWithTwoChildren(eraser->data, previous, eraser);
            }
        }
    }

    //////////////////////////////////////////////////////////////////////
    //                      void RemoveLeaf()                           //
    //////////////////////////////////////////////////////////////////////

    void RemoveLeaf(Node<T>* previous, Node<T>* eraser)
    {
        if (eraser && previous)
        {
            //see if parent's got any other children
            if (previous->link_left == eraser && previous->link_right)
            {
                previous->link_left = nullptr;
            }
            else if (previous->link_left && previous->link_right == eraser)
            {
                previous->link_right = nullptr;
            }
            else
            {
                previous->link_left = nullptr;
                previous->link_right = nullptr;
            }
            delete eraser;
            --m_size;
        }
    }

    //////////////////////////////////////////////////////////////////////
    //              void RemoveWithOneChild()                           //
    //////////////////////////////////////////////////////////////////////

    void RemoveWithOneChild(Node<T>* previous, Node<T>* eraser)
    {
        if (previous && eraser)
        {
            if (eraser->link_right)
            {
                Node<T>* temp = eraser->link_right;
                if (previous->link_right == eraser)
                {
                    previous->link_right = temp;
                }
                else
                {
                    previous->link_left = temp;
                }
                temp->link_left = nullptr;
                temp->link_right = nullptr;
                delete eraser;
                --m_size;
            }
            else if (eraser->link_left)
            {
                Node<T>* temp = eraser->link_left;
                if (previous->link_right == eraser)
                {
                    previous->link_right = temp;
                }
                else
                {
                    previous->link_left = temp;
                }
                //previous->link_left = temp;
                temp->link_left = nullptr;
                temp->link_right = nullptr;
                delete eraser;
                --m_size;
            }


        }
    }

    //////////////////////////////////////////////////////////////////////
    //              void RemoveWitheTwoChildren()                       //
    //////////////////////////////////////////////////////////////////////

    void RemoveWithTwoChildren(T data, Node<T>* previous, Node<T>* eraser)
    {
        if (!eraser)
        {
            return;
        }
        //move the furthest down to the smallest node from the right child.
        //change its value with the node to erase and erase it.
        Node<T>* tempR = eraser->link_right;
        while (tempR->link_left)
        {
            tempR = tempR->link_left;
        }
        eraser->data = tempR->data;
        if (!tempR->link_right)
        {
            delete tempR;
            eraser->link_right = nullptr;//testing
            --m_size;
        }
        else if (tempR->link_right)
        {
            //swap data value
            Node<T>* tempRCopy = tempR;
            Node<T>* tempRR = tempR->link_right;
            tempR->data = tempRR->data;
            tempRR->data = tempRCopy->data;

            //now the replacer is a leaf and on the wrong side.
            //remove that
            delete tempR->link_right;
            tempR->link_right = nullptr;
            --m_size;
        }
    }

    //////////////////////////////////////////////////////////////////////
    //                          int size()                              //
    //////////////////////////////////////////////////////////////////////

    int size()
    {
        return m_size;
    }

    //////////////////////////////////////////////////////////////////////
    //                  void Traversal_pre_order()                      //
    //////////////////////////////////////////////////////////////////////

    void Traversal_pre_order(NodePtr node) // typename Node<T>* NodePtr;
    {
        //Start with the root, than every left node first, than every right node
        //recursive. Inspired by classmates
        if (!node)
        {
            return;//exit this function call and return to previous recursive call
        }

        std::cout << node->data << ", "; //print data

        Traversal_pre_order(node->link_left); // first the left nodes will be printed

        Traversal_pre_order(node->link_right); // then, the right nodes will be printed

        // the recursive loop will print the left nodes first until a nullptr link is reached
        // then it will back up and try the right nodes for every time a left node has been printed
        // until it hits a nullptr node. this will finally print all the nodes one by one.
    }

    //////////////////////////////////////////////////////////////////////
    //                  void Traversal_post_order()                     //
    //////////////////////////////////////////////////////////////////////

    void Traversal_post_order(NodePtr node) // typename Node<T>* NodePtr;
    {
        //exit condition
        if (!node)
        {
            return;
        }

        // starting with the left "children" until the first nullptr
        Traversal_post_order(node->link_left);

        // then the right "childeren" for every left child, in reverse order
        Traversal_post_order(node->link_right);

        // when all right children of the left children have had their recursive calls,
        // and has not been nullptr, print their data

        std::cout << node->data << ", ";
    }

    //////////////////////////////////////////////////////////////////////
    //                  void Traversal_in_order()                       //
    //////////////////////////////////////////////////////////////////////

    void Traversal_in_order(NodePtr node) // typename Node<T>* NodePtr;
    {
        if (!node)
        {
            return;
        }

        //in order - from small to large.
        //start by going left all the way
        Traversal_in_order(node->link_left);

        //after a nullptr hit, go back, print data and find out if there are any right children
        // that have left children.
        std::cout << node->data << ", ";
        //for every node that have a right child, go to the left most node and print them first
        Traversal_in_order(node->link_right);

    }

    void delete_post_order(NodePtr node)
    {
        if (!node)
        {
            return;
        }
        delete_post_order(node->link_left);
        delete_post_order(node->link_right);
        delete node;
    }
};