#pragma once
using namespace std;

struct elem {
    int value;
    elem *left, *right;
};

class searchTree {
private:
    elem *tree;
    int counter = 0;
public:
    searchTree() {
        tree = nullptr;
    }
    ~searchTree() {
        delete_helper(tree);
    }

    void delete_helper(elem *tree) {
        if (tree != nullptr) {
            delete_helper(tree->left);
            delete_helper(tree->right);
            delete tree;
        }
    }

    void show_pre() {
        show_pre_helper(tree);
    }

    void show_pre_helper(elem *tree) {
        if (tree) {
            cout << tree -> value << endl;
            show_pre_helper(tree->left);
            show_pre_helper(tree->right);
        }
    }

    void show_in() {
        show_in_helper(tree);
    }

    void show_in_helper(elem *tree) {
        if (tree) {
            show_in_helper(tree->left);
            cout << tree -> value << endl;
            show_in_helper(tree->right);
        }
    }

    void show_post() {
        show_post_helper(tree);
    }

    void show_post_helper(elem *tree) {
        if (tree) {
            show_post_helper(tree->left);
            show_post_helper(tree->right);
            cout << tree -> value << endl;
        }
    }

    int min() {
        cout << min_helper(tree) << endl;
        return min_helper(tree);
    }

    int min_helper(elem *tree) {
        while (tree->left != nullptr)
            tree = tree -> left;
        return tree -> value;
    }

    int max() {
        cout << max_helper(tree) << endl;
        return max_helper(tree);
    }

    int max_helper(elem *tree) {
        while (tree->right != nullptr)
            tree = tree -> right;
        return tree -> value;
    }

    void add(int x) {
        add_helper(x, tree);
    }

    void add_helper(int x, elem *&tree) {
        if (tree == nullptr) {
            tree = new elem;
            tree -> value = x;
            tree -> left = tree -> right = nullptr;
        }
        if (x < tree -> value) {
            add_helper (x, tree -> left);
        }
        if (x > tree -> value) {
            add_helper (x, tree -> right);
        }
    }

    void remove(int x) {
        remove_helper(x, tree);
    }

    void remove_helper(int x, elem *&tree) {
        if (tree -> value == x) {
            elem *node = tree;
            if (tree -> left == nullptr && tree -> right == nullptr) {
                tree = 0;
                delete node;
            }
            else {
                if (tree -> left == nullptr) {
                    tree = tree -> right;
                    delete node;
                }
                else {
                    if (tree -> right == nullptr) {
                        tree = tree -> left;
                        delete node;
                    }
                    else {
                        elem *p = tree;
                        elem *i = tree -> left;
                        int count = 0;
                        while (i -> right != nullptr)
                        {
                            p = i;
                            i = i -> right;
                            count++;
                        }
                        tree->value = i->value;
                        if (count)
                            p -> right = i -> left;
                        else
                            p -> left = i -> left;
                        delete_helper(i);
                    }
                }
            }
        }
        else {
            if (x < tree -> value)
                remove_helper(x, tree->left);
            else
                remove_helper(x, tree->right);
        }
    }
};



int main() {
    searchTree tree;
    int elems = 0, choice = 0, show = 0, del = 0;
    char exit = 0;
    do {
        cout<<"1. Добавить узел в дерево"<<endl
        <<"2. Обойти дерево"<<endl
        <<"3. Удалить узел дерева"<<endl
        <<"4. Вывести минимальное значение дерева"<<endl
        <<"5. Вывести максимальное значение дерева"<<endl
        <<"0. Завершить программу"<<endl
        <<"Выберите один из пунктов: ";
        cin >> choice;
        switch (choice) {
            case 0:
                return 0;

            case 1:
                cout << "Введите количество элементов, которое вы хотите добавить в дерево: ";
                cin >> elems;
                cout << "Вводите " << elems << " элементов: ";
                for (int i = 0, m; i < elems; i++) {
                    cin >> m;
                    tree.add(m);
                }
                break;

            case 2:
                cout<<"Выберите обход: "<<endl
                <<"1. Префиксный"<<endl
                <<"2. Инфиксный"<<endl
                <<"3. Постфиксный"<<endl;
                cin >> show;
                switch (show) {
                    case 1:
                        tree.show_pre();
                        break;
                    case 2:
                        tree.show_in();
                        break;
                    case 3:
                        tree.show_post();
                        break;
                }
                break;

            case 3:
                cout << "Введите значение удаляемого узла: ";
                cin >> del;
                tree.remove(del);
                cout << "Ваше дерево без элемента " << del << endl;
                tree.show_in();
                break;

            case 4:
                tree.min();
                break;

            case 5:
                tree.max();
                break;

            default:
                cout << "Такого пункта нет!" << endl;
        }
        cout<<"Вы хотите выбрать еще какой-либо пункт? (Y/N)"<<endl;
        cin >> exit;
    } while (exit == 'y');

    return 0;
}