Untitled

#include <iostream>
using namespace std;
class TreeNode {
public:
    int data;          
    TreeNode* left;    
    TreeNode* right;     

    TreeNode(int val) {
        data = val;
        left = right = NULL;
    }
};

// insert a new node into the tree
TreeNode* insert(TreeNode* root, int data) {
    // if the tree is empty, create a new node and return it
    if (root == NULL) {
        return new TreeNode(data);
    }

    // if data is less than root data, insert it in the left subtree
    if (data < root->data) {
        root->left = insert(root->left, data);
    }
    // if data is greater than root data, insert it in the right subtree
    else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;  // Return the root of the subtree
}

// Find the node with the minimum value (used for deletion)
TreeNode* findMin(TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// delete a node from the tree
TreeNode* deleteNode(TreeNode* root, int data) {
    // if the tree is empty, return NULL
    if (root == NULL) {
        return root;
    }

    // if the data to be deleted is smaller than root's data, it's in the left subtree
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    }
    // If the data to be deleted is greater than root's data, it's in the right subtree
    else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    }
    // If the data is equal to root's data, we've found the node to delete
    else {
        // case 1: Node has no children (leaf node)
        if (root->left == NULL && root->right == NULL) {
            delete root;
            root = NULL;
        }
        // case 2: Node has only one child
        else if (root->left == NULL) {
            TreeNode* temp = root;
            root = root->right;
            delete temp;
        }
        else if (root->right == NULL) {
            TreeNode* temp = root;
            root = root->left;
            delete temp;
        }
        // case 3: Node has two children
        else {
            //  the inorder successor
            TreeNode* temp = findMin(root->right);
            root->data = temp->data;  // replace the root's data with the inorder successor
            root->right = deleteNode(root->right, temp->data);  // Delete the inorder successor
        }
    }

    return root;  // Return the updated root 
}

// Inorder traversal to display the BST (left-root-right)
void inorder(TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);      
        cout << root->data << " "; 
        inorder(root->right);     
    }
}

// Search for a node 
TreeNode* search(TreeNode* root, int key) {
    // tree is empty or the key is found at the root
    if (root == NULL || root->data == key) {
        return root;
    }

    // search in the left subtree
    if (key < root->data) {
        return search(root->left, key);
    }

    return search(root->right, key);
}

// Function to print the result of the search
void searchNode(TreeNode* root, int key) {
    TreeNode* result = search(root, key);
    if (result != NULL) {
        cout << "Node with value " << key << " found in the tree." << endl;
    } else {
        cout << "Node with value " << key << " not found in the tree." << endl;
    }
}

int main() {
    TreeNode* root = NULL;  
    int choice, value;

    while (true) {
        
        cout << "*******\nMenu:\n********";
        cout << "1. Insert a node\n";
        cout << "2. Delete a node\n";
        cout << "3. Display tree (Inorder Traversal)\n";
        cout << "4. Search for a node\n";
        cout << "5. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                // Insert a node
                cout << "Enter value to insert: ";
                cin >> value;
                root = insert(root, value);
                cout << "Node inserted successfully!\n";
                break;

            case 2:
                // Delete a node
                cout << "Enter value to delete: ";
                cin >> value;
                root = deleteNode(root, value);
                cout << "Node deleted successfully if it exists!\n";
                break;

            case 3:
                // Display 
                cout << "Inorder Traversal of the tree: ";
                inorder(root);
                cout << endl;
                break;

            case 4:
                // Search for a node
                cout << "Enter value to search: ";
                cin >> value;
                searchNode(root, value);
                break;

            case 5:
                // Exit the program
                cout << "Exiting the program...\n";
                exit(0);

            default:
                cout << "Invalid choice! Please try again.\n";
        }
    }

    return 0;
}