#include <iostream>

using namespace std;

class Node{
    private:
        int v;
        Node* left_node;
        Node* right_node;
        Node* parent_node;
    public:
        Node(int v, Node* l, Node* r){ this->v = v; left_node=l; right_node=r; parent_node=NULL;}
        int value()
        {
            return v;
        }
        Node* left()
        {
            return left_node;
        }
        Node* right()
        {
            return right_node;
        }
        Node* parent()
        {
            return parent_node;
        }
        void setValue(int v)
        {
            Node::v = v;
        }
        void setLeft(Node* l)
        {
            left_node = l;
        }
        void setRight(Node* r)
        {
            right_node = r;
        }
        void setParent(Node* p)
        {
            parent_node = p;
        }
};

class Tree{
    private:
        Node* root;

        bool empty(Node* n)
        {
            if(n == nullptr) return true;
            else return false;
        }   //zwraca prawdê gdy wêze³ nie istnieje
        void preorder(Node* n)
        {
            if(n != nullptr) cout<< n->value() << ", ";
            if(n->left() != nullptr) preorder(n->left());
            if(n->right() != nullptr) preorder(n->right());
        }
        void inorder(Node* n)
        {
            if(n->left() != nullptr) inorder(n->left());
            if(n != nullptr) cout<< n->value() << ", ";
            if(n->right() != nullptr) inorder(n->right());
        }
        void postorder(Node* n)
        {
            if(n->left() != nullptr) postorder(n->left());
            if(n->right() != nullptr) postorder(n->right());
            if(n != nullptr) cout<< n->value() << ", ";
        }
    public:
        Tree()
        {
            root = nullptr;
        }           //tworzy puste drzewo
        Tree(Node* r)
        {
            root = r;
        }
        bool empty()
        {
            if(root == nullptr) return true;
            else return false;
        }       //zwraca prawdê gdy drzewo jest puste
        void preorder()
        {
            preorder(root);
        }
        void inorder()
        {
            inorder(root);
        }
        void postorder()
        {
            postorder(root);
        }


};

class TreeBST
{
        private:
        Node* root;

        bool empty(Node* n)
        {
            if(n == nullptr) return true;
            else return false;
        }   //zwraca prawdê gdy wêze³ nie istnieje

        void preorder(Node* n)
        {
            if(n != nullptr) cout<< n->value() << ", ";
            if(n->left() != nullptr) preorder(n->left());
            if(n->right() != nullptr) preorder(n->right());
        }
        void inorder(Node* n)
        {
            if(n->left() != nullptr) inorder(n->left());
            if(n != nullptr) cout<< n->value() << ", ";
            if(n->right() != nullptr) inorder(n->right());
        }
        void postorder(Node* n)
        {
            if(n->left() != nullptr) postorder(n->left());
            if(n->right() != nullptr) postorder(n->right());
            if(n != nullptr) cout<< n->value() << ", ";
        }
        Node* minimum(Node* c)
        {
            if(c==nullptr) return nullptr;
            while(c->left() != nullptr) c = c->left();
            return c;
        }

        Node* maximum(Node* c)
        {
            if(c==nullptr) return nullptr;
            while(c->right() != nullptr) c = c->right();
            return c;
        }
        public:
        TreeBST()
        {
            root = nullptr;
        }           //tworzy puste drzewo
        TreeBST(Node* r)
        {
            root = r;
        }
        bool empty()
        {
            if(root == nullptr) return true;
            else return false;
        }       //zwraca prawdê gdy drzewo jest puste
        void insert(int x)
        {
            Node * n = new Node(x, nullptr, nullptr);
            Node *p = root;
            Node *s = p;
            if(empty()) root = n;
            else
            {
                while(p != nullptr)
                {
                s = p;
                if(p->value() > n->value()) p = p->left();
                else p = p->right();
                }
                if(s->value() > n->value()) s->setLeft(n);
                else s->setRight(n);
            }
            n->setParent(s);
        }

        Node* search(int x)
        {
            if(root == nullptr) return nullptr;
            else
            {
                Node * c = root;
                while(c != nullptr)
                {
                if(c->value() > x) c = c->left();
                else if(c->value() < x) c = c->right();
                else return c;
                }
                return nullptr;
            }
        }

        Node* minimum()
        {
            Node *c = root;
            if(c==nullptr) return nullptr;
            while(c->left() != nullptr) c = c->left();
            return c;
        }

        Node* maximum()
        {
            Node *c = root;
            if(c==nullptr) return nullptr;
            while(c->right() != nullptr) c = c->right();
            return c;
        }

        Node* prec(Node* p)
        {
            if(p->left() != nullptr) maximum(p->left());
            else
            {
                while(p->parent() != nullptr)
                {
                if(p->parent()->left() == p) p = p->parent();
                else return p->parent();
                }
            }
        }

        Node* succ(Node* p)
        {
            if(p->right() != nullptr) minimum(p->right());
            else
            {
                while(p->parent() != nullptr)
                {
                if(p->parent()->right() == p) p = p->parent();
                else return p->parent();
                }
            }
        }

        void del(Node* p)
        {
            if((p->left() == nullptr)&&(p->right()==nullptr))
            {
            if(p->parent()->left() == p) p->parent()->setLeft(nullptr);
            if(p->parent()->right() == p) p->parent()->setRight(nullptr);
            delete p;
            }
            else if(p->left() == nullptr)
            {
                Node *o = p;
                p = p->right();
                p->setParent(o->parent());
                delete o;
            }
            else if(p->right() == nullptr)
            {
                Node *o = p;
                p = p->left();
                p->setParent(o->parent());
                delete o;
            }
        }

        void preorder()
        {
            preorder(root);
        }
        void inorder()
        {
            inorder(root);
        }
        void postorder()
        {
            postorder(root);
        }

};

/*
przyk³adowe drzewo do testów (bez ustawienia ojca):
    Tree* t=new Tree(new Node(9, new Node(5, new Node(2, new Node(3, NULL, NULL), new Node(3, NULL, NULL)),
    new Node(7, NULL, new Node(8,NULL, NULL))), new Node(12, new Node(10, NULL, new Node(11, NULL, NULL)), NULL)));

*/

int main()
{
    TreeBST* t = new TreeBST();
    t->insert(12);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(7);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(9);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(3);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(19);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(15);
    cout << "\nPreorder: ";
    t->preorder();
    t->insert(14);
    cout << "\nPreorder: ";
    t->preorder();
    cout << endl;
    t->del(t->search(15));
    cout << "\nPreorder: ";
    t->preorder();

}