#include <iostream>
#include <ctime>
#include <cmath>

using namespace std;
/**
 * Визначити, чи входить заданий елемент до дерева.
 */
struct Node {
    int x = 0;
    Node *left;
    Node *right;
};

/**
 * Показати Дерево
 * @param tree Делево
 */
void showTree(Node *&tree) {
    if (tree != NULL) {
        showTree(tree->left);
        cout << tree->x << endl;
        showTree(tree->right);
    }
}

/**
 * додати Node
 * @param x
 * @param tree Делево
 */
void addNode(int x, Node *&tree) {
    if (NULL == tree) {
        tree = new Node;
        tree->x = x;
        tree->left = tree->right = NULL;
    }
    if (x < tree->x) {
        if (tree->left != NULL) {
            addNode(x, tree->left);
        } else {
            tree->left = new Node;
            tree->left->left = tree->left->right = NULL;
            tree->left->x = x;
        }
    }
    if (x > tree->x) {
        if (tree->right != NULL) {
            addNode(x, tree->right);
        } else {
            tree->right = new Node;
            tree->right->left = tree->right->right = NULL;
            tree->right->x = x;
        }
    }

}

/**
 *
 * @param tree Делево
 * @param number число
 * @param check перевірка
 */
void workerFindElements(Node *&tree, int number, bool &check) {
    if (tree != NULL) {
        if (tree->x == number) {
            check = true;
        }
        workerFindElements(tree->left, number, check);
        workerFindElements(tree->right, number, check);
    }
};

/**
 *
 * @param tree Делево
 * @param number число
 * @return checkElement
 */
bool findElement(Node *&tree, int number) {
    bool checkElement = false;
    workerFindElements(tree, number, checkElement);
    return checkElement;
}

/**
 *
 * @param tree Делево
 */
void delTree(Node *&tree) {
    if (tree != NULL) {
        delTree(tree->left);
        delTree(tree->right);
        delete tree;
        tree = NULL;
    }
}

/**
    * Мы должні узнать если элемент в дереве
    * С начала заполняем рандомом, потом спрашиваем у пользователя элемент.
    * Потом ищем в новом дереве и выводим результат нашли мы его или нет
 * @return 0
 */
int main() {
    Node *tree = NULL;
    srand(time(0));
    int number;

    for (int i = 0; i < 20; i++) {
        addNode(rand(), tree);
    }

    showTree(tree); // показать дерево

    cout << "-------------" << endl;
    cout << "Enter number" << endl;
    cin >> number; // Просим вести что-то
    string result = findElement(tree, number) ? "Element found" : "Element not found"; // результат
    cout << result << endl;

    delTree(tree); // удаления дерева

    system("pause"); //для удобства

    return 0;
}