#include <iostream>
#include <queue>
#include <stack>

struct Nod
{
    int info;
    Nod* st, *dr, *parinte;
    Nod(int info)
    {
        this->info = info;
        st = dr = parinte = nullptr;
    }
};

class searchTree
{
public:
    Nod* rad;

    searchTree()
    {
        rad = nullptr;
    }


    void insert(int cheie)
    {
        if (rad == nullptr)
        {
            rad = new Nod(cheie);
        }

        else
        {
            Nod* x = rad;
            Nod* parinteNodNou = nullptr;
            while (x != nullptr)
            {
                parinteNodNou = x;
                if (cheie < x->info)
                    x = x->st;
                else
                    x = x->dr;
            }

            Nod* z = new Nod(cheie);
            z->parinte = parinteNodNou;
            if (z->info < parinteNodNou->info)
                parinteNodNou->st = z;
            else
                parinteNodNou->dr = z;
        }
    }

    Nod* minim(Nod* x)
    {
        Nod* y = x;
        while (y->st != nullptr)
            y = y->st;
        return y;
    }

    Nod* maxim(Nod* x)
    {
        Nod* y = x;
        while (y->dr != nullptr)
            y = y->dr;
        return y;
    }

    Nod* succesor(Nod* x)
    {
        Nod* y;
        if (x->dr != nullptr)
            y = minim(x->dr);
        else
        {
            y = x->parinte;
            while (y != nullptr && x == y->dr)
            {
                x = y;
                y = y->parinte;
            }

        }
        return y;
    }

    Nod* predecesor(Nod* x)
    {
        Nod* y;
        if (x->st != nullptr)
            y = minim(x->st);
        else
        {
            y = x->parinte;
            while (y != nullptr && x == y->st)
            {
                x = y;
                y = y->parinte;
            }

        }
        return y;
    }

    Nod* find(int cheie)
    {
        Nod* x = rad;
        while (x != nullptr && x->info != cheie)
        {
            if (cheie < x->info)
                x = x->st;
            else
                x = x->dr;
        }
        return x;
    }


    void deleteNode(int cheie)
    {
        Nod* nodCurent = rad;
        Nod* prev = NULL;

        while (nodCurent != NULL && nodCurent->info != cheie)
        {
            prev = nodCurent;
            if (cheie < nodCurent->info)
                nodCurent = nodCurent->st;
            else
                nodCurent = nodCurent->dr;
        }

        if (nodCurent == NULL)
        {
            std::cout << "Nodul cu cheia  " << cheie << " nu exista in arbore";
            return;
        }

        if (nodCurent->st == NULL || nodCurent->dr == NULL)
        {
            Nod* newCurr;

            if (nodCurent->st == NULL)
                newCurr = nodCurent->dr;
            else
                newCurr = nodCurent->st;

            if (prev == NULL)
                return;

            if (nodCurent == prev->st)
                prev->st = newCurr;
            else
                prev->dr = newCurr;

            free(nodCurent);
        }

        //daca nodul curent are doi copii
        else
        {
            Nod* p = succesor(rad);
            Nod* temp;

            temp = nodCurent->dr;
            while (temp->dr != NULL) {
                p = temp;
                temp = temp->st;
            }


            if (p != NULL)
                p->st = temp->dr;
            else
                nodCurent->dr = temp->dr;

            nodCurent->info = temp->info;
            free(temp);
        }

        return;
    }

    void erase(Nod* x)
    {
        if (find(x->info))
            deleteNode(find(x->info)->info);
    }

    void print_tree(int opt)
    {
        //afisare in preordine
        if (opt == 1)
            preordine(rad);
        if (opt == 2)
            inordine(rad);
        if (opt == 3)
            postordine(rad);
        std::cout << '\n';
    }


    void construct()
    {

    }

    void empty()
    {
        if (rad->st == nullptr && rad->dr == nullptr)
            std::cout << "arborele este vid";
        else std::cout << "arborele nu este vid";
    }

    void clear()
    {
        if (rad == nullptr)
            return;

        std::queue<Nod*> coada;
        coada.push(rad);

        Nod* front = nullptr;

        while (!coada.empty())
        {

            front = coada.front();
            deleteNode(front->info);
        }
    }

private:
    void preordine(Nod* nod)
    {
        if (nod == nullptr)
            return;
        preordine(nod->st);
        preordine(nod->dr);
        std::cout << nod->info << ' ';
    }

    void inordine(Nod* nod)
    {
        if (nod == nullptr)
            return;
        preordine(nod->st);
        std::cout << nod->info << ' ';
        preordine(nod->dr);
    }

    void postordine(Nod* nod)
    {
        if (nod == nullptr)
            return;
        std::cout << nod->info << ' ';
        preordine(nod->st);
        preordine(nod->dr);
    }

};

int main()
{
    searchTree a;
    bool continua = true;
    while (continua)
    {
        std::cout << "1. insert(cheie)\n";
        std::cout << "2. print_tree(opt)\n";

        int alegere, cheie;
        Nod* rad;
        std::cin >> alegere;
        switch (alegere)
        {
        case 1:
            std::cout << "cheie = ";
            std::cin >> cheie;
            a.insert(cheie);
            break;
        case 2:
            a.print_tree(1);
            break;
        }
    }
    return 0;
}