Binary Search Tree in C++ [FULL]

// AUTHOR : Fueanta
// Implementation of BST in CPP
// Last Modified : September 16, 2017 (Generic BST Data Structure, Node count)
// Contact EMAIL : fueanta@gmail.com [let me know if you find any bug]

#include <iostream>
#include <string>
#include <stdlib.h>
#include <queue>

using std::queue;
using namespace std;

void menu();

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

template <class T>
class tree_node {
public:
    T key;
    tree_node<T> *left, *right;
};

template <class T>
class bst
{
    tree_node<T>* root_;
    int count_;
    bool deletion_;

public:
    bst()
    {
        root_ = nullptr;
        count_ = 0;
        deletion_ = false;
    }

    void tree_initiate();
    tree_node<T>* make_node(T);
    void create_tree();
    void insert_node();
    void insert_engine(tree_node<T>* &, T);
    void delete_node();
    void delete_engine(tree_node<T>* &, T);
    void search_node();
    tree_node<T>* search_engine(tree_node<T>*, T);
    static tree_node<T>* find_max(tree_node<T>*); void find_max();
    static tree_node<T>* find_min(tree_node<T>*); void find_min();
    void delete_tree(tree_node<T>*&); void delete_tree();
    void pre_order(tree_node<T>*); void pre_order();
    void in_order(tree_node<T>*); void in_order();
    void post_order(tree_node<T>*); void post_order();
    void disp_tree(tree_node<T>*); void disp_tree();
    int count_nodes() const;

    friend void menu();
};

bst<int> bin; /* ##### -|-|CHANGE BST TYPE HERE|-|- ##### */

template <typename T>
void bst<T>::tree_initiate() {
    if (root_ != nullptr)
        delete_tree(root_);
    deletion_ = false;
    this->count_ = 0;
}

template <typename T>
tree_node<T>* bst<T>::make_node(T data) {
    tree_node<T>* node_ptr = new tree_node<T>;
    if (node_ptr == nullptr) {
        cout << "\nOut of memory." << endl;
        return nullptr;
    }
    else {
        cout << "\nMemory allocated for a new node." << endl;
        node_ptr->key = data; node_ptr->left = node_ptr->right = nullptr;
        ++this->count_;
        return node_ptr;
    }
}

template <typename T>
void bst<T>::create_tree() {
    tree_initiate();
    cout << "\n*** How many elements will be on the new tree? Elements: ";
    int n; cin >> n;
    for (auto i = 0; i < n; i++) {
        cout << "\nElement " << i + 1 << ": ";
        T data; cin >> data;
        insert_engine(root_, data);
    }
    cout << "\n*** New Tree has been created with " << n << " elements." << endl;
}

template <typename T>
void bst<T>::insert_node() {
    if (root_ != nullptr) {
        cout << "\n*** Which element do you wish to insert into the BST? Data value: ";
        T data; cin >> data;
        insert_engine(root_, data);
        cout << "\n*** Element " << data << " has been inserted." << endl;
    }
    else cout << "\nCreate a BST first. [Choice no: 1]" << endl;
}

template <typename T>
void bst<T>::insert_engine(tree_node<T>* &node, T data) {
    if (node == nullptr)
        node = make_node(data);
    else if (data < node->key)
        insert_engine(node->left, data);
    else if (data > node->key)
        insert_engine(node->right, data);
}

template <typename T>
void bst<T>::delete_node() {
    if (root_ != nullptr) {
        cout << "\n*** Which element do you wish to delete from the BST? Element: ";
        T data; cin >> data;
        delete_engine(root_, data);
        if (deletion_ == true) {
            cout << "\nElement " << data << " just got deleted." << endl;
            --this->count_;
            deletion_ = false;
        }
        else
            cout << "\nElement " << data << " could not be found so operation failed." << endl;
    }
    else cout << "\n*** Deletetion cannot be done. [Empty Tree]" << endl;
}

template <typename T>
void bst<T>::delete_engine(tree_node<T>* &node, T data) {
    if (node != nullptr) {
        if (data < node->key)
            delete_engine(node->left, data);
        else if (data > node->key)
            delete_engine(node->right, data);
        else {
            deletion_ = true;
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                node = nullptr;
            }
            else if (node->left == nullptr) {
                tree_node<T>* temp = node;
                node = node->right;
                delete temp;
            }
            else if (node->right == nullptr) {
                tree_node<T>* temp = node;
                node = node->left;
                delete temp;
            }
            else {
                tree_node<T>* temp = find_max(node->left); // or, find_min(node->right);
                node->key = temp->key;
                delete_engine(node->left, temp->key);
                // or, DeleteEngine(node->right, temp->key);
            }
        }
    }
}

template <typename T>
void bst<T>::delete_tree() {
    if (root_ == nullptr)
        cout << "\nOperation cannot be done. [Empty Tree]" << endl;
    else {
        delete_tree(root_);
        cout << "\nTree has been deleted." << endl;
    }
}

template <typename T>
void bst<T>::delete_tree(tree_node<T>* &node) {
    if (node != nullptr) {
        delete_tree(node->left);
        delete_tree(node->right);
        delete node;
        node = nullptr;
    }
    this->count_ = 0;
}

template <typename T>
void bst<T>::search_node() {
    if (root_ != nullptr) {
        cout << "\n*** Which element do you wish to search in the BST? Element: ";
        T data; cin >> data;
        tree_node<T> * node = search_engine(root_, data);
        if (node == nullptr)
            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;
}

template <typename T>
tree_node<T>* bst<T>::search_engine(tree_node<T>* node, T data) {
    if (node != nullptr) {
        if (data < node->key)
            node = search_engine(node->left, data);
        else if (data > node->key)
            node = search_engine(node->right, data);
    }
    return node;
}

template <typename T>
void bst<T>::find_min() {
    if (root_ != nullptr)
        cout << "\nMin: " << find_min(root_)->key << endl;
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
tree_node<T>* bst<T>::find_min(tree_node<T>* node) {
    while (node->left != nullptr)
        node = node->left;
    return node;
}

template <typename T>
void bst<T>::find_max() {
    if (root_ != nullptr)
        cout << "\nMax: " << find_max(root_)->key << endl;
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
tree_node<T>* bst<T>::find_max(tree_node<T>* node) {
    while (node->right != nullptr)
        node = node->right;
    return node;
}

template <typename T>
void bst<T>::pre_order() {
    if (root_ != nullptr) {
        cout << "\nPre-Order: ";
        pre_order(root_); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
void bst<T>::pre_order(tree_node<T>* node) {
    if (node != nullptr) {
        cout << node->key << " ";
        pre_order(node->left);
        pre_order(node->right);
    }
}

template <typename T>
void bst<T>::in_order() {
    if (root_ != nullptr) {
        cout << "\nIn-Order: ";
        in_order(root_); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
void bst<T>::in_order(tree_node<T>* node) {
    if (node != nullptr) {
        in_order(node->left);
        cout << node->key << " ";
        in_order(node->right);
    }
}

template <typename T>
void bst<T>::post_order() {
    if (root_ != nullptr) {
        cout << "\nPost-Order: ";
        post_order(root_); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
void bst<T>::post_order(tree_node<T>* node) {
    if (node != nullptr) {
        post_order(node->left);
        post_order(node->right);
        cout << node->key << " ";
    }
}

template <typename T>
void bst<T>::disp_tree() {
    if (root_ != nullptr) {
        cout << "\nBST by level: ";
        disp_tree(root_); cout << endl;
    }
    else cout << "\nOperation cannot be done. [Empty Tree]" << endl;
}

template <typename T>
void bst<T>::disp_tree(tree_node<T>* node) {
    queue <tree_node<T>*> bst;
    bst.push(node);
    while (!bst.empty()) {
        if (bst.front()->left != nullptr)
            bst.push(bst.front()->left);
        if (bst.front()->right != nullptr)
            bst.push(bst.front()->right);
        cout << bst.front()->key << " ";
        bst.pop();
    }
    cout << endl;
}

template <typename T>
int bst<T>::count_nodes() const
{
    return count_;
}

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 {{Ascending Order}}.\n09. Post-Order Traverse.\n10. Display by Levels.\n11. Delete Tree.\n12. Show total number of nodes.\n13. EXIT !" << endl;
    int choice; cout << "\nChoose : "; cin >> choice;

    switch (choice) {
    case 1: bin.create_tree();
        break;
    case 2: bin.insert_node();
        break;
    case 3: bin.delete_node();
        break;
    case 4: bin.search_node();
        break;
    case 5: bin.find_max();
        break;
    case 6: bin.find_min();
        break;
    case 7: bin.pre_order();
        break;
    case 8: bin.in_order();
        break;
    case 9: bin.post_order();
        break;
    case 10: bin.disp_tree();
        break;
    case 11: bin.delete_tree();
        break;
    case 12: cout << "\nTotal number of nodes: " << bin.count_nodes() << endl;
        break;
    case 13: cout << "\nTerminating ....\n\n";
        bin.delete_tree(bin.root_);
        exit(0);
    default: cout << "\nWrong Choice. [Choose between 1 - 13]\n" << endl;
        menu();
    }
}