Binary Search Tree Remove Method - C++

Binary Search Tree

That organizes elements in a hierarchical manner, allowing efficient search, insertion, and deletion operations. It is a specialized form of a binary tree in which the keys (values) stored in the nodes follow a specific order.

The Binary Search Tree (BST) Remove Method

That allows you to remove a specific node from a binary search tree while maintaining the BST property.
The remove method typically takes two parameters: the root node of the tree and the value to be removed.

Explanation

1. Define the Node structure:

It contains an integer data field and pointers to the left and right child nodes.

2. Implement the createNode function:

This function creates a new node with the given data value.
It allocates memory for the node, sets its data value, and initializes the left and right pointers to nullptr.
The function returns the newly created node.

3. Implement the insertNode function:

This function inserts a new node with the given data into the BST.
It takes the current root node and the data as parameters.
If the root is nullptr, indicating an empty tree or a leaf node, it calls the createNode function to create a new node and returns it.
If the data is less than the root’s data, the function recursively inserts the data into the left subtree.
If the data is greater than the root’s data, it recursively inserts the data into the right subtree. Finally, it returns the modified root node.

4. Implement the findMinNode function:

This function finds the node with the minimum value in a given subtree.
It takes the root of the subtree as a parameter and iteratively traverses the left child pointers until it reaches the leftmost node (which will have the minimum value).
The function returns the node with the minimum value.

5. Implement the deleteNode function:

This function deletes a node with the given data.
It takes the current root node and the data as parameters.
If the root is nullptr, indicating an empty tree or the node was not found, it simply returns the root.
If the data is less than the root’s data, the function recursively deletes the data from the left subtree.
If the data is greater than the root’s data, it recursively deletes the data from the right subtree.
If the data is equal to the root’s data, the function performs the deletion logic.
If the root has no or only one child, it adjusts the pointers and deletes the node.
If the root has two children, it finds the minimum value node in the right subtree, replaces the root’s data with that node’s data, and recursively deletes the minimum value node from the right subtree.
Finally, it returns the modified root node.

6. Implement the inorderTraversal function:

This function performs an inorder traversal of the BST, printing the values of the nodes in ascending order.
It takes the current root node as a parameter.
It recursively traverses the left subtree, prints the data of the current node, and then recursively traverses the right subtree.

7. Implement the main function:

The main function serves as the entry point of the program.
It starts by initializing the root pointer to nullptr and declares variables for user input (choice and data).

8. Inside the main loop:

Pogram displays a menu of options for BST operations and prompts the user for their choice. The user’s choice is stored in the choice variable using std::cin.

9. User’s Choice:

Case 1: Insertion – The program prompts the user to enter the data value to be inserted. It calls the insertNode function with the current root and the user’s data. The modified root is then assigned back to the root pointer.
Case 2: Deletion – The program prompts the user to enter the data value to be removed. It calls the deleteNode function with the current root and the user’s data. The modified root is then assigned back to the root pointer.
Case 3: Inorder Traversal – The program calls the inorderTraversal function with the current root to print the BST’s elements in ascending order.
Case 4: Exit – The program exits by returning 0 from the main function.

10. Invalid Choice:

The program displays an error message and returns to the beginning of the loop.

				
					#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

// Function to insert a node into the BST
Node* insertNode(Node* root, int data) {
    if (root == nullptr) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// Function to find the minimum value node in a subtree
Node* findMinNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

// Function to delete a node from the BST
Node* deleteNode(Node* root, int data) {
    if (root == nullptr) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // Node found, perform deletion
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        // Node has two children, find the minimum value node from the right subtree
        Node* temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// Function to perform inorder traversal of the BST
void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = nullptr;
    int choice, data;

    while (true) {
        std::cout << "Binary Search Tree Operations:\n";
        std::cout << "1. Insert Node\n";
        std::cout << "2. Remove Node\n";
        std::cout << "3. Print Inorder Traversal\n";
        std::cout << "4. Exit\n";
        std::cout << "Enter your choice: ";
        std::cin >> choice;

        switch (choice) {
            case 1:
                std::cout << "Enter data to insert: ";
                std::cin >> data;
                root = insertNode(root, data);
                break;
            case 2:
                std::cout << "Enter data to remove: ";
                std::cin >> data;
                root = deleteNode(root, data);
                break;
            case 3:
                std::cout << "Inorder Traversal: ";
                inorderTraversal(root);
                std::cout << std::endl;
                break;
            case 4:
                // Free memory and exit the program
                // ...
                return 0;
            default:
                std::cout << "Invalid choice. Please try again.\n";
        }
    }
}

Binary Search Tree Remove Method – C++