Lecture 301:- Deleting from Binary Search Tree

Deleting a node from a Binary Search Tree (BST) involves maintaining the BST property after the deletion. There are three cases to consider when deleting a node from a BST:

1. Node with no children (Leaf node): In this case, we simply remove the node from the tree.
2. Node with one child: We replace the node with its child.
3. Node with two children: We find the inorder successor (or predecessor) of the node to be deleted, copy its value to the node, and then recursively delete the inorder successor.

Here's the C++ implementation for deleting a node from a BST:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; // Function to find the inorder successor of a given node TreeNode* findInOrderSuccessor(TreeNode* root) {    TreeNode* curr = root->right;    while (curr != nullptr && curr->left != nullptr) {        curr = curr->left;    }    return curr; } // Function to delete a node from the BST TreeNode* deleteBST(TreeNode* root, int key) {    if (root == nullptr)        return root;    // If the key is smaller than the root's key, go to the left subtree    if (key < root->val)        root->left = deleteBST(root->left, key);    // If the key is greater than the root's key, go to the right subtree    else if (key > root->val)        root->right = deleteBST(root->right, key);    // If the key is the same as the root's key, this is the node to be deleted    else {        // Case 1: Node with only one child or no child        if (root->left == nullptr) {            TreeNode* temp = root->right;            delete root;            return temp;        } else if (root->right == nullptr) {            TreeNode* temp = root->left;            delete root;            return temp;        }        // Case 2: Node with two children        // Get the inorder successor (smallest in the right subtree)        TreeNode* successor = findInOrderSuccessor(root);        // Copy the value of the inorder successor to this node        root->val = successor->val;        // Delete the inorder successor        root->right = deleteBST(root->right, successor->val);    }    return root; } void inOrderTraversal(TreeNode* root) {    if (root == nullptr)        return;    inOrderTraversal(root->left);    cout << root->val << " ";    inOrderTraversal(root->right); } int main() {    // Create a binary search tree:    //        5    //       / \    //      3   8    //     / \ / \    //    2  4 7  9    TreeNode* root = new TreeNode(5);    root->left = new TreeNode(3);    root->right = new TreeNode(8);    root->left->left = new TreeNode(2);    root->left->right = new TreeNode(4);    root->right->left = new TreeNode(7);    root->right->right = new TreeNode(9);    // Perform an in-order traversal to see the original BST    cout << "In-order Traversal of BST (Before Deletion): ";    inOrderTraversal(root);    cout << endl;    // Delete node with value 3 from the BST    int keyToDelete = 3;    root = deleteBST(root, keyToDelete);    // Perform an in-order traversal to see the updated BST    cout << "In-order Traversal of BST (After Deletion): ";    inOrderTraversal(root);    cout << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right->left;    delete root->right->right;    delete root->right;    delete root;    return 0; }

Output:

mathematicaCopy code

In-order Traversal of BST (Before Deletion): 2 3 4 5 7 8 9 In-order Traversal of BST (After Deletion): 2 4 5 7 8 9

In this code, we perform the deletion of a node with value 3 from the BST. After the deletion, we perform an in-order traversal to see the updated BST. Note that the in-order traversal of the BST is still in ascending order, indicating that the BST property is maintained after the deletion.