binarySearchTree.cpp

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

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

node *st[100];
int TOS = -1;

void mainMenu()
{
    cout << "\n ===========================Main Menu===========================" << endl;
    cout << " 1. Insert Node" << endl;
    cout << " 2. Delete Node" << endl;
    cout << " 3. Search Node" << endl;
    cout << " 4. PreOrder Travesal" << endl;
    cout << " 5. InOrder Travesal" << endl;
    cout << " 6. PostOrder Travesal" << endl;
    cout << " 10. Exit" << endl;
    cout << "Enter your choice: " << endl;
}

node *Insert(node *root, int key)
{
    if (root == nullptr)
    {
        node *ptr = new node();
        ptr->data = key;
        return ptr;
    }
    if (root->data > key)
        root->left = Insert(root->left, key);

    if (root->data <= key)
        root->right = Insert(root->right, key);

    return root;
}
node *Delete(node *root, int key)
{
    node *temp = root;
    node *parent = nullptr;

    while (temp != nullptr && temp->data != key)
    {
        parent = temp;
        if (key < temp->data)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }

    if (root == nullptr)
    {
        return root;
    }

    // Case 1: Leaf node
    if (temp->left == nullptr && temp->right == nullptr)
    {
        if (temp == root)
        {
            delete temp;
            root = nullptr;
        }
        else if (parent->left == temp)
        {
            parent->left = nullptr;
            delete temp;
        }
        else
        {
            parent->right = nullptr;
            delete temp;
        }
    }

    // Case 2: node with only left subtree
    else if (temp->right == nullptr)
    {
        if (temp == root)
        {
            root = temp->left;
        }
        else if (parent->left == temp)
        {
            parent->left = temp->left;
        }
        else
        {
            parent->right = temp->left;
        }
        delete temp;
    }

    // Case 3: node with only right subtree
    else if (temp->left == nullptr)
    {
        // node to be deleted is root node
        if (temp == root)
        {
            root = temp->right;
        }
        else if (parent->left == temp)
        {
            parent->left = temp->right;
        }
        else
        {
            parent->right = temp->right;
        }
        delete temp;
    }

    // Case 4: node with both the subtrees
    else
    {
        node *replacement = temp->right;
        node *RightParent = temp;
        // Finding minimum node in the right subtree of the node to be deleted
        while (replacement->left != nullptr)
        {
            RightParent = replacement;
            replacement = replacement->left;
        }
        temp->data = replacement->data;
        if (RightParent->left == replacement)
        {
            RightParent->left = replacement->right;
        }
        else
        {
            RightParent->right = replacement->right;
        }
        delete replacement;
    }
    return root;
}

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

void InOrderTraversal(node *root)
{ // left->node->right
    if (root == nullptr)
        return;
    InOrderTraversal(root->left);
    cout << root->data << " ";
    InOrderTraversal(root->right);
}
void PostOrderTraversal(node *root)
{ // left->right->node
    if (root == nullptr)
        return;
    PostOrderTraversal(root->left);
    PostOrderTraversal(root->right);
    cout << root->data << " ";
}
node *searchElement(node *root, int key)
{
    if (root == nullptr)
        return nullptr;
    if (root->data == key)
        return root;
    if (root->data < key)
        return searchElement(root->right, key);
    if (root->data > key)
        return searchElement(root->left, key);
    return nullptr;
}
int main()
{
    node *root = nullptr;
    int userChoice = 0;

    while (userChoice != 10)
    {
        mainMenu();
        cin >> userChoice;
        switch (userChoice)
        {
        case 1:
            int data;
            cout << "Enter the data to insert: " << endl;
            cin >> data;
            root = Insert(root, data);
            InOrderTraversal(root);
            break;
        case 2:
        {

            int key;
            cout << "Enter the element to Delete: ";
            cin >> key;
            Delete(root, key);
            PreOrderTraversal(root);
            break;
        }
        case 3:
        {
            int key;
            cout << "Enter the element to search: ";
            cin >> key;
            searchElement(root, key) ? cout << "Element found"
                                     : cout << "Element not found.";
        }
        case 4:
            PreOrderTraversal(root);
            break;
        case 5:
            InOrderTraversal(root);
            break;
        case 6:
            PostOrderTraversal(root);
            break;
        case 10:
            cout << "Exiting...";
            userChoice = 10;
            break;
        default:
            break;
        }
    }
    return 0;
}