Simple Implementation of a Binary Search Tree(C++)

BinarySearchTree.cpp

#include <bits/stdc++.h>
 using namespace std;

struct node {
    int data{};
    node* left = nullptr;
    node* right = nullptr;
};

class BinarySearchTree{
    node* root;

    public:
        BinarySearchTree() { root = nullptr; }

        node* GetRoot() { return root; }

        void InsertNode(int stuff) {
           if(root == nullptr){
               root = new node();
               root->data = stuff;
               cout << "Element inserted.\n";
               root->left = root->right = nullptr;
           }
           else {
               auto parent = GetRoot();
               node * temp;
               temp = new node();
               temp->data = stuff;

               while(parent != nullptr){
                   if(parent->data > stuff){
                       if(parent->left == nullptr){
                           parent->left = temp;
                           cout << "Element inserted.\n"; break; }
                       else { parent = parent->left; }
                   } else {
                       if(parent->right == nullptr){
                           parent->right = temp;
                           cout << "Element inserted.\n"; break; }
                       else { parent = parent->right; }
                   }
               }
           }
        }

        void inorderTreeWalk(node *temp) {
            if(temp == nullptr){ return; }
            inorderTreeWalk(temp->left);
            cout <<  " -> " << temp->data;
            inorderTreeWalk(temp->right); }

        void preorderTreeWalk(node *temp) {
            if(temp == nullptr){ return; }
            cout << " -> " << temp->data;
            preorderTreeWalk(temp->left);
            preorderTreeWalk(temp->right); }

        void postorderTreeWalk(node *temp) {
            if(temp == nullptr){ return; }
            postorderTreeWalk(temp->left);
            postorderTreeWalk(temp->right);
            cout << " -> " << temp->data; }

        node* TreeMin(node* temp) {
            if(temp == nullptr){ return nullptr; }
            while(temp->left) { temp = temp->left; }
            return temp;
        }

        node* TreeMax(node* temp) {
            while(temp->right != nullptr) { temp = temp->right; }
            return temp;
        }

        node* TreeSearch(int stuff) {
            auto temp = GetRoot();
            if(temp == nullptr) { return nullptr; }

            while(temp) {
                if(stuff == temp->data){ return temp; }
                else if(stuff < temp->data){ temp = temp->left; }
                else { temp = temp->right; }
            }
            return nullptr;
        }

        node* Successor(int data) {
            node* current = TreeSearch(data);
            if(current == nullptr){ return nullptr; }
            if(current->right){ return TreeMin(current->right); }

            node* temp = GetRoot();
            node* succ = nullptr;

            while(temp){
                if(current->data < temp->data){
                    succ = temp;
                    temp = temp->left;
                } else if(current->data > temp->data){ temp = temp->right; }
                else { break; }
            }
            return succ;
        }

        node* Predecessor(int data) {
            node* current = TreeSearch(data);
            if(current == nullptr){ return nullptr; }
            if(current->right){ return TreeMax(current->left); }

            node* temp = GetRoot();
            node* succ = nullptr;

            while(temp){
                if(current->data < temp->data){
                    temp = temp->left;
                } else if(current->data > temp->data){ succ = temp; temp = temp->right; }
                else { break; }
            }
            return succ;
        }

        void RemoveNode(node* parent, node* curr, int stuff) {
            if(curr == nullptr) { return; }
            if(curr->data == stuff) {
                //CASE -- 1
                if(curr->left == nullptr && curr->right == nullptr){
                    if(parent->data == curr->data){ root = nullptr; }
                    else if(parent->right == curr){ parent->right = nullptr; }
                    else { parent->left = nullptr; }
                }
                //CASE -- 2
                else if(curr->left != nullptr && curr->right == nullptr) {
                    int swap = curr->data;
                    curr->data = curr->left->data;
                    curr->left->data = swap;
                    RemoveNode(curr, curr->right, stuff);
                }
                else if(curr->left == nullptr && curr->right != nullptr) {
                    int swap = curr->data;
                    curr->data = curr->right->data;
                    curr->right->data = swap;
                    RemoveNode(curr, curr->right, stuff);
                }
                //CASE -- 3
                else {
                    bool flag = false;
                    node* temp = curr->right;
                    while(temp->left){ flag = true; parent = temp; temp = temp->left; }
                    if(!flag){ parent = curr; }
                    int swap = curr->data;
                    curr->data = temp->data;
                    temp->data = swap;
                    RemoveNode(parent, temp, swap);
                }
            }
        }

        void Remove(int stuff){
            auto temp = root;
            auto parent = temp;
            bool flag = false;
            if(temp == nullptr){ RemoveNode(nullptr, nullptr, stuff); }

            while(temp) {
                if(stuff == temp->data){ flag = true; RemoveNode(parent, temp, stuff); break; }
                else if(stuff < temp->data){ parent = temp ; temp = temp->left; }
                else { parent = temp ; temp = temp->right; }
            }

            if(!flag){ cout << "\nElement doesn't exist in the table"; }
        }

        void menu(){
            cout << "\n___________________________________________";
            cout << "\n\n         --BINARY SEARCH TREE--";
            cout << "\n___________________________________________";
            cout << "\n\n1. Insert elements into the tree.";
            cout << "\n2. Search for an element.";
            cout << "\n3. Find Successor of an element.";
            cout << "\n4. Find Predecessor of an element.";
            cout << "\n5. In-order Tree-Walk.";
            cout << "\n6. Pre-order Tree-Walk.";
            cout << "\n7. Post-order Tree-Walk.";
            cout << "\n8. Remove an element from the tree.";
            cout << "\n9. Exit.";
            cout << "\n___________________________________________";
            cout << "\nYour Choice -- ";
        }
};

int main(){
    BinarySearchTree demo;
    int info, input;
    demo.menu();

    cin >> info;
    while(info != 9){
        switch (info){
            case 1: cout << "\nElement to be inserted -- ";
                    cin >> input; demo.InsertNode(input);
                    break;

            case 2: cout << "\nElement to be searched -- ";
                    cin >> input;
                    if(demo.TreeSearch(input)) { cout << "Element found.\n"; }
                    else { cout << "Element not found.\n"; }
                    break;

            case 3: cout << "\nElement whose Successor is to be found -- ";
                    cin >> input;
                    if(demo.Successor(input)) {
                        cout << "Successor of " << input << " in the tree is " << demo.Successor(input)->data << endl; }
                    else { cout << "\nSuccessor of that element doesn't exist in the tree.\n"; }
                    break;

            case 4: cout << "\nElement whose Predecessor is to be found -- ";
                    cin >> input;
                    if(demo.Predecessor(input)) {
                        cout << "Predecessor of " << input << " in the tree is " << demo.Predecessor(input)->data << endl; }
                    else { cout << "Predecessor of that element doesn't exist in the tree.\n"; }
                    break;

            case 5: cout << "In-Order Traversal of the tree ";
                    demo.inorderTreeWalk(demo.GetRoot());
                    cout << endl;
                    break;

            case 6: cout << "Pre-Order Traversal of the tree ";
                    demo.preorderTreeWalk(demo.GetRoot());
                    cout << endl;
                    break;

            case 7: cout << "Post-Order Traversal of the tree ";
                    demo.postorderTreeWalk(demo.GetRoot());
                    cout << endl;
                    break;

            case 8: cout << "Element to be deleted? -- ";
                    cin >> input;
                    demo.Remove(input);
                    cout << endl;
                    break;

            default: cout << "Wrong Choice.\n";
        }
        cout << "\nAnything Else?";
        cin >> info;
    }
    cout << "\nTerminating.... ";
}