Binary Search Tree in C++ Programming

BinarySearchTree.cpp

/*
    Binary Search Tree : A binary tree in which all the nodes are arranged according to their values is known as Binary Search Tree.
    In this program we will see the code to create, insert an node, delete a node in a Binary Search Tree.
*/

#include<iostream>
using namespace std;

// Data Structure for Binary tree's nodes.
struct BinarySearchTree
{
    int data;                                           // Stores the Data value
    BinarySearchTree *right = NULL, *left = NULL;       // Stores the right and left subtree addresses.
};

class BST
{
    // Declaring the Private Variables.
    private:
        BinarySearchTree *root = NULL, *temp = NULL, *newNode;
    public:
        void display();
        void create();
        void insert();
        void Delete();
        void menu();
        void run();
        void inordertraverse(BinarySearchTree *temp);
        void preordertraverse(BinarySearchTree *temp);
        void postordertraverse(BinarySearchTree *temp);
};

void BST::display()
{
    system("cls");
    cout<<"\t\t\t\tBinary Search Tree"<<endl;
    cout<<"\t\t\t  A Program by Aman Singh Bhogal"<<endl;
    for(int i=0;i<80;i++)
        cout<<"_";
    cout<<endl<<endl;
}

void BST::menu()
{
    cout<<endl<<"Menu:"<<endl;
    cout<<"1. Insert New Node."<<endl;
    cout<<"2. Delete a Node."<<endl;
    cout<<"3. Inorder Traverse the BST."<<endl;
    cout<<"4. Preorder Traverse the BST."<<endl;
    cout<<"5. Postorder Traverse the BST."<<endl;
    cout<<"6. Exit."<<endl;
    cout<<"Note: The code for deleting an element with both children is still pending."<<endl;
}

void BST::create()
{
    int n;
    cout<<"Enter the Value to be inserted: ";
    cin>>n;
    newNode = new BinarySearchTree;
    newNode->data = n;
    insert();
}

void BST::insert()
{
    // Base Case if the tree is Empty insert a root node.
    if(root == NULL)
        root = newNode;
    // If Tree is not empty.
    else
    {
        temp = root;
        while(temp != NULL)
        {
            if(newNode->data < temp->data)
            {
                if(temp->left == NULL)
                {
                    temp->left = newNode;
                    break;
                }
                else
                    temp = temp->left;
            }
            else
            {
                if(temp->right == NULL)
                {
                    temp->right = newNode;
                    break;
                }
                else
                    temp = temp->right;
            }
        }
    }
}

// In order traversal recursive code
void BST::inordertraverse(BinarySearchTree *temp)
{
    if(temp->left != NULL)
        inordertraverse(temp->left);
    cout<<temp->data<<" -> ";
    if(temp->right != NULL)
        inordertraverse(temp->right);
}

// Pre order traversal Recursive code
void BST::preordertraverse(BinarySearchTree *temp)
{
    cout<<temp->data<<" -> ";
    if(temp->left != NULL)
        preordertraverse(temp->left);
    if(temp->right != NULL)
        preordertraverse(temp->right);
}

// Post order traversal recursive code.
void BST::postordertraverse(BinarySearchTree *temp)
{
    if(temp->left != NULL)
        postordertraverse(temp->left);
    if(temp->right != NULL)
        postordertraverse(temp->right);
    cout<<temp->data<<" -> ";
}

void BST::Delete()
{
    int n;
    cout<<endl<<"Enter the Data value of Node to be Deleted: ";
    cin>>n;
    // Case #1 When the Node to be deleted is a Leaf Node.
    temp = root;
    while(temp != NULL)
    {
        cout<<endl<<temp->data<<endl;
        
        if(temp->left != NULL)
        {
            if(temp->left->data == n) 
            {
                // Case #1 Condition for Leaf Node being the Node to delete:
                if(temp->left->left == NULL && temp->left->right == NULL)
                {
                    free(temp->left);
                    temp->left = NULL;
                    break;
                }
                // Case #2 Condition for Node with only one child.
                else if(temp->left->left == NULL || temp->left->right == NULL)
                {
                    newNode = temp->left;
                    if(temp->left->left == NULL)
                        temp->left = temp->left->right;
                    else
                        temp->left = temp->left->left;
                    free(newNode);
                    break;
                }
            }
        }
        else if(temp->right!=NULL)
        {
            if(temp->right->data == n) 
            {
                // Case #1 Condition for Leaf Node being the Node to delete:
                if (temp->right->left == NULL && temp->right->right == NULL)
                {
                    free(temp->right);
                    temp->right = NULL;
                    break;
                }
                // Case #2 Condition for Node with only one child.
                else if(temp->right->left == NULL || temp->right->right == NULL)
                {
                    newNode = temp->right;
                    if(temp->right->left == NULL)
                        temp->right = temp->right->right;
                    else
                        temp->right = temp->right->left;
                    free(newNode);
                    break;
                }
            }
        }
        if (n < temp->data)
            temp = temp->left;  
        else
            temp = temp->right;
    }
    cout<<"The tree after Node deletion is: "<<endl;
    inordertraverse(root);
}

void BST::run()
{
    char ch = 'y';
    do{
        display();
        int choice;
        menu();
        cout<<endl<<"Enter your choice: ";
        cin>>choice;
        switch(choice)
        {
            case 1: create();
            break;
            case 2: Delete();
            break;
            case 3: inordertraverse(root);
            break;
            case 4: preordertraverse(root);
            break;
            case 5: postordertraverse(root);
            break;
            case 6: exit(0);
            break;
        }
        cout<<endl<<"Do you want to continue? [y/n]: ";
        cin>>ch;
    }while(ch == 'y');
}

int main()
{
    BST B;
    B.run();
    return 0;
}