#ifndef __BINARY_SEARCH_TREE_H
#define __BINARY_SEARCH_TREE_H

#include <iostream>

using namespace std;

template <class T>
class BinarySearchTree
{
private:

    struct Node
    {
        T key_;
        Node* left_;
        Node* right_;
        Node* p_;

        Node(const T& key, Node* p = nullptr, Node* left = nullptr, Node* right = nullptr) : key_(key), left_(left), right_(right), p_(p) {}
    };

    Node* root_;

public:

    BinarySearchTree() : root_(nullptr) {}

    virtual ~BinarySearchTree()
    {
        deleteSubtree(root_);
    }

    void print(ostream& out) const
    {
        printNode(out, root_);
        out << endl;
    }

    void iterativeInsert(const T& key)
    {
        Node* n = new Node(key);
        Node* ptr;
        Node* ptr1;

        n->p_ = n->left_ = n->right_ = 0;
        ptr = root_;

        ptr1 = nullptr;

        while (ptr != 0)
        {
            ptr1 = ptr;
            if (key < ptr->key_)
            {
                ptr = ptr->left_;
            }
            else
            {
                ptr = ptr->right_;
            }
        }
        n->p_ = ptr1;
        if (ptr1 == 0)
        {
            root_ = n;
        }
        else
        {
            if (key < ptr1->key_)
            {
                ptr1->left_ = n;
            }
            else
            {
                ptr1->right_ = n;
            }
        }
    }

    void recursiveInsert(const T& key)
    {
        recursiveInsert(root_, key);
    }

    bool iterativeSearch(const T& key) const
    {
        return (iterativeSearchNode(key) != nullptr);
    }

    T getSuccsessor(const T& key)
    {
        Node* x = iterativeSearchNode(key);
        Node* y;
        if (x->right_ != nullptr)
        {
            return searchMin(x)->key_;
        }
        y = x->p_;
        while (y != nullptr && x == y->right_)
        {
            x = y;
            y = y->p_;
        }
        if (y != nullptr)
        {
            return y->key_;
        }
        else
        {
            cout << "nullptr";
            return -1;
        }
    }

    int getCount() const
    {
        return getCountSubTree(this->root_);
    }

    int getHeight()
    {
        return getHeightSubTree(root_);
    }

    void deleteKey(const T& key)
    {
        deleteKey(root_, key);
    }

    void inorderWalk() const
    {
        orderWalk(root_);
    }

private:

    Node* searchMin(Node* x)
    {
        while (x->left_ != nullptr)
        {
            x = x->left_;
        }
        return x;
    }

    void printNode(ostream& out, Node* root) const
    {
        out << '(';
        if (root != nullptr)
        {
            out << root->key_;
            printNode(out, root->left_);
            printNode(out, root->right_);
        }
        out << ')';
    }

    void recursiveInsert(Node*& node, const T& key)
    {
        if (node == nullptr)
        {
            node = new Node(key);
        }
        else
        {
            if (key < node->key_)
            {
                recursiveInsert(node->left_, key);
            }
            else
            {
                recursiveInsert(node->right_, key);
            }
        }
    }

    Node* iterativeSearchNode(const T& key) const
    {
        Node* current = root_;

        while (true)
        {
            if (current == nullptr)
            {
                return nullptr;
            }
            if (current->key_ == key)
            {
                return current;
            }

            if (key < current->key_)
            {
                current = current->left_;
            }
            else
            {
                current = current->right_;
            }
        }
    }

    Node* searchSuccsessor(const T& key)
    {
        Node* x = iterativeSearchNode(key);
        Node* y;
        if (x->right_ != nullptr)
        {
            return searchMin(x);
        }
        y = x->p_;
        while (y != nullptr && x == y->right_)
        {
            x = y;
            y = y->p_;
        }

        return y;
    }

    int getCountSubTree(Node* node) const
    {
        if (node == nullptr)
        {
            return 0;
        }
        return (1 + getCountSubTree(node->left_) + getCountSubTree(node->right_));
    }

    int getHeightSubTree(Node* node)
    {
        if (node == nullptr)
        {
            return 0;
        }
        int left, right;
        if (node->left_ != nullptr)
        {
            left = getHeightSubTree(node->left_);
        }
        else
        {
            left = -1;
        }
        if (node->right_ != nullptr)
        {
            right = getHeightSubTree(node->right_);
        }
        else
        {
            right = -1;
        }
        int max = left > right ? left : right;
        return max + 1;
    }

    void deleteSubtree(Node* node)
    {
        if (node == nullptr) return;

        deleteSubtree(node->left_);
        deleteSubtree(node->right_);

        delete node;
    }

    Node* deleteKey(Node* toDelete, const T& key)
    {
        if (toDelete == nullptr)
        {
            return toDelete;
        }

        if (key == toDelete->key_)
        {
            Node* current;
            if (toDelete->right_ == nullptr)
            {
                current = toDelete->left_;
            }
            else
            {

                Node* ptr = toDelete->right_;
                if (ptr->left_ == nullptr)
                {
                    ptr->left_ = toDelete->left_;
                    current = ptr;
                }
                else
                {
                    Node* pMin = ptr->left_;
                    while (pMin->left_ != nullptr)
                    {
                        ptr = pMin;
                        pMin = ptr->left_;
                    }
                    ptr->left_ = pMin->right_;
                    pMin->left_ = toDelete->left_;
                    pMin->right_ = toDelete->right_;
                    current = pMin;
                }
            }
            delete toDelete;
            return current;
        }
        else if (key < toDelete->key_)
        {
            toDelete->left_ = deleteKey(toDelete->left_, key);
        }
        else
        {
            toDelete->right_ = deleteKey(toDelete->right_, key);
        }

        return toDelete;
    }

    void orderWalk(Node* node) const
    {
        if (node != nullptr)
        {
            orderWalk(node->left_);
            cout << node->key_ << endl;
            orderWalk(node->right_);
        }
    }
};

#endif