#define NOMINMAX
#include <iostream>
#include <limits>
#include <string>
#include <conio.h>
#include <Windows.h>
using namespace std;
struct Tree {
    int key;
    string inf;
    Tree *left;
    Tree *right;
};
bool isKeyUnique(Tree *tree, int key);
int menu();
void addElement(Tree *&tree, string a, int b);
void deleteTree(Tree *&tree);
void exitProgram();
void inputNumber(int &a);
void searchMinAndMaxElements(Tree *tree, int &min, int &max);
void searchNearestElements(Tree *tree, int average, int &dif, Tree *&temp);
void showTree(Tree *tree, int level, bool isEmpty);
int main() {
    Tree *root = NULL, *temp;
    string a;
    int b, min, max, average, dif;
    bool isEmpty = true;
    while (true) {
        switch (menu()) {
        case 1:
            cout << "Enter the string" << endl;
            cin >> a;
            cout << "Enter the key" << endl;
            inputNumber(b);
            addElement(root,a,b);
            cout << "Element added" << endl;
            break;
        case 2:
            cout << "\t\tTree" << endl;
            showTree(root, 0, isEmpty);
            if (isEmpty) {
                cout << "Tree is empty" << endl;
            }
            break;
        case 3:
            deleteTree(root);
            cout << "Tree deleted" << endl;
            break;
        case 4:
            min = root->key;
            max = root->key;
            temp = root;
            searchMinAndMaxElements(root, min, max);
            cout << "min - " << min << endl;
            cout << "max - " << max << endl;
            average = (min + max) / 2;
            cout << "av = "<<average << endl;
            dif = root->key - average;
            searchNearestElements(root, average, dif, temp);
            cout << "Nearest to middle = " << temp->key << endl;
            break;
        case 5:
            exitProgram();
            break;
        default:
            cout << "Choose 1-5!" << endl;
            break;
        }
    }
    return 0;
}
int menu() {
    int choise;
    cout << "1 - add" << endl;
    cout << "2 - show" << endl;
    cout << "3 - delete tree" << endl;
    cout << "4 - Search the nearest to average element" << endl;
    cout << "5 - exit" << endl;
    inputNumber(choise);
    return choise;
}
void showTree(Tree *tree, int level, bool isEmpty) {
    string str;
    if (tree != NULL) {
        isEmpty = false;
        showTree(tree->right, level+1, isEmpty);
        for (int i = 0; i < level; i++) {
            str += "    ";
        }
        cout << str << tree->inf << " " << tree->key << endl;
        showTree(tree->left, level+1, isEmpty);
    }
}
void addElement(Tree *&tree, string a, int b) {
    if (!isKeyUnique(tree, b)) {
        return;
    }
    if (tree == NULL) {
        tree = new Tree;
        tree->inf = a;
        tree->key = b;
        tree->left = NULL;
        tree->right = NULL;
    }
    else if (b<tree->key){
        addElement(tree->left, a, b);
    }
    else {
        addElement(tree->right, a, b);
    }
}
void deleteTree(Tree *&tree) {
    if (tree != NULL) {
        deleteTree(tree->left);
        deleteTree(tree->right);
        delete tree;
        tree = NULL;
    }
}
bool isKeyUnique(Tree *tree, int key) {
    bool flag = true;
    while (tree && flag) {
        if (key == tree->key) {
            flag = false;
            cout << "Such key already exists" << endl;
        }
        else {
            if (key < tree->key) {
                tree = tree->left;
            }
            else {
                tree = tree->right;
            }
        }
    }
    return flag;
}
void inputNumber(int &a) {
    while (true) {
        cin >> a;
        if (cin.get() == '\n') {
            break;
        }
        cout << "Wrong input. Please, try again!" << endl;
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }
}
void exitProgram() {
    cout << "Press Enter if you want to exit" << endl;
    if (_getch() == 13) {
        exit(0);
    }
}
void searchMinAndMaxElements(Tree *tree, int &min, int &max) {
    if (tree != NULL) {
        searchMinAndMaxElements(tree->right, min, max);
        if (tree->key > max) {
            max = tree->key;
        }
        else if (tree->key < min) {
            min = tree->key;
        }
        searchMinAndMaxElements(tree->left, min, max);
    }
}
void searchNearestElements(Tree *tree, int mid, int &dif, Tree *&temp) {
    if (tree != NULL) {
        searchNearestElements(tree->right, mid, dif, temp);
        if (abs(dif) > abs(tree->key - mid)) {
            dif = abs(tree->key - mid);
            temp = tree;
        }
        searchNearestElements(tree->left, mid, dif, temp);
    }
}