BST Implementation in C++

// AUTHOR : Fueanta
// Implementation of BST in CPP
// First of its kind. Updated later
// Contact EMAIL : fueanta@gmail.com [let me know if you find any bug]

#include <iostream>
#include <stdlib.h>
using namespace std;

struct TreeNode {
    int key;
    TreeNode *left, *right;
} *root;

bool deletion;

TreeNode* MakeNode(int);
void CreateTree();
void InsertNode();
void InsertEngine(TreeNode* &, int);
void DeleteNode();
void DeleteEngine(TreeNode* &, int);
void SearchNode();
TreeNode* SearchEngine(TreeNode*, int);
TreeNode* find_max(TreeNode*); void find_max();
TreeNode* find_min(TreeNode*); void find_min();
void DeleteTree(TreeNode*&); void DeleteTree();
void PreOrder(TreeNode* node); void PreOrder();
void InOrder(TreeNode* node); void InOrder();
void PostOrder(TreeNode* node); void PostOrder();
void menu();

void treeInitiate() {
    if (root != NULL)
        DeleteTree(root);
    deletion = false;
}

int main() {
    menu();
    cout << endl;
    main();
    return 0;
}

TreeNode* MakeNode(int data) {
    TreeNode* NodePtr = new TreeNode;
    if (NodePtr == NULL) {
        cout << "\nOut of memory." << endl;
        return NULL;
    }
    else {
        cout << "\nMemory allocated for a new node." << endl;
        NodePtr->key = data; NodePtr->left = NodePtr->right = NULL;
        return NodePtr;
    }
}

void CreateTree() {
    cout << "\n*** How many elements will be on the new tree? Elements: ";
    int n; cin >> n;
    treeInitiate();
    for (int i = 0; i < n; i++) {
        cout << "\nElement " << i + 1 << ": ";
        int data; cin >> data;
        InsertEngine(root, data);
    }
    cout << "\n*** New Tree has been created with " << n << " elements." << endl;
}

void InsertNode() {
    if (root != NULL) {
        cout << "\n*** Which element do you wish to insert into the BST? Data value: ";
        int data; cin >> data;
        InsertEngine(root, data);
        cout << "\n*** Element " << data << " has been inserted." << endl;
    }
    else cout << "\nCreate a BST first. [Choice no: 1]" << endl;
}

void InsertEngine(TreeNode* &node, int data) {
    if (node == NULL)
        node = MakeNode(data);
    else if (data < node->key)
        InsertEngine(node->left, data);
    else if (data > node->key)
        InsertEngine(node->right, data);
}

void DeleteNode() {
    if (root != NULL) {
        cout << "\n*** Which element do you wish to delete from the BST? Element: ";
        int data; cin >> data;
        DeleteEngine(root, data);
        if (deletion == true) {
            cout << "\nElement " << data << " just got deleted." << endl;
            deletion = false;
        }
        else
            cout << "\nElement " << data << " could not be found so operation failed." << endl;
    }
    else cout << "\n*** Deletetion cannot be done. [Empty Tree]" << endl;
}

void DeleteEngine(TreeNode* &node, int data) {
    if (node != NULL) {
        if (data < node->key)
            DeleteEngine(node->left, data);
        else if (data > node->key)
            DeleteEngine(node->right, data);
        else {
            deletion = true;
            if (node->left == NULL && node->right == NULL) {
                delete node;
                node = NULL;
            }
            else if (node->left == NULL) {
                TreeNode* temp = node;
                node = node->right;
                delete temp;
                temp = NULL;
            }
            else if (node->right == NULL) {
                TreeNode* temp = node;
                node = node->left;
                delete temp;
                temp = NULL;
            }
            else {
                TreeNode* temp = find_max(node->left); // find_min(node->right);
                node->key = temp->key;
                DeleteEngine(node->left, temp->key);
                // node->right = DeleteEngine(node->right, temp->key);
            }
        }
    }
}

void DeleteTree() {
    if (root == NULL)
        cout << "\nOperation cannot be done. [Empty Tree]" << endl;
    else {
        DeleteTree(root);
        cout << "\nTree has been deleted." << endl;
    }
}

void DeleteTree(TreeNode* &node) {
    if (node != NULL) {
        DeleteTree(node->left);
        DeleteTree(node->right);
        delete node;
        node = NULL;
    }
}

void SearchNode() {
    if (root != NULL) {
        cout << "\n*** Which element do you wish to search in the BST? Element: ";
        int data; cin >> data;
        TreeNode* node;
        node = SearchEngine(root, data);
        if (node == NULL)
            cout << "\nGiven element could not be found in your tree." << endl;
        else cout << "\nGiven element " << data << " has been found." << endl;
    }
    else cout << "\n*** Search cannot be done. [Empty Tree]" << endl;
}

TreeNode* SearchEngine(TreeNode* node, int data) {
    if (node != NULL) {
        if (data < node->key)
            node = SearchEngine(node->left, data);
        else if (data > node->key)
            node = SearchEngine(node->right, data);
    }
    return node;
}

void find_min() {
    if (root != NULL)
        cout << "\nMin: " << find_min(root)->key << endl;
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

TreeNode* find_min(TreeNode* node) {
    while (node->left != NULL)
        node = node->left;
    return node;
}

void find_max() {
    if (root != NULL)
        cout << "\nMax: " << find_max(root)->key << endl;
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

TreeNode* find_max(TreeNode* node) {
    while (node->right != NULL)
        node = node->right;
    return node;
}

void PreOrder() {
    if (root != NULL) {
        cout << "\nPre-Order: ";
        PreOrder(root); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

void PreOrder(TreeNode* node) {
    if (node != NULL) {
        cout << node->key << " ";
        PreOrder(node->left);
        PreOrder(node->right);
    }
}

void InOrder() {
    if (root != NULL) {
        cout << "\nIn-Order: ";
        InOrder(root); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

void InOrder(TreeNode* node) {
    if (node != NULL) {
        InOrder(node->left);
        cout << node->key << " ";
        InOrder(node->right);
    }
}

void PostOrder() {
    if (root != NULL) {
        cout << "\nPost-Order: ";
        PostOrder(root); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

void PostOrder(TreeNode* node) {
    if (node != NULL) {
        PostOrder(node->left);
        PostOrder(node->right);
        cout << node->key << " ";
    }
}

void menu() {
    cout << "Choice List: " << endl;
    cout << "\n01. Create a new BST.\n02. Insert into BST.\n03. Delete from BST.\n04. Search in BST."
        << "\n05. Maximum value in BST.\n06. Minimum value in BST.\n07. Pre-Order Traverse."
        << "\n08. In-Order Traverse.\n09. Post-Order Traverse.\n10. DELETE TREE\n11. EXIT !" << endl;
    int choice; cout << "\nChoose : "; cin >> choice;

    switch (choice) {
    case 1: CreateTree();
        break;
    case 2: InsertNode();
        break;
    case 3: DeleteNode();
        break;
    case 4: SearchNode();
        break;
    case 5: find_max();
        break;
    case 6: find_min();
        break;
    case 7: PreOrder();
        break;
    case 8: InOrder();
        break;
    case 9: PostOrder();
        break;
    case 10: DeleteTree();
        break;
    case 11: cout << "\nTerminating ....\n\n";
        DeleteTree(root);
        exit(0);
    default: cout << "\nWrong Choice. [Choose between 1 - 10]\n" << endl;
        menu();
    }
}