Lecture 302:- Let's Code Recursive Insert and Delete on BST

Here's the C++ implementation of recursive insertion and deletion in a Binary Search Tree (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) {} }; // Recursive function to insert a new node in the BST TreeNode* insertBST(TreeNode* root, int val) {    if (root == nullptr)        return new TreeNode(val);    if (val < root->val)        root->left = insertBST(root->left, val);    else if (val > root->val)        root->right = insertBST(root->right, val);    return root; } // Recursive 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; } // Recursive 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 an empty binary search tree    TreeNode* root = nullptr;    // Insert nodes into the binary search tree    root = insertBST(root, 5);    root = insertBST(root, 3);    root = insertBST(root, 8);    root = insertBST(root, 2);    root = insertBST(root, 4);    root = insertBST(root, 7);    root = insertBST(root, 9);    // Perform an in-order traversal to see the sorted 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.    // You can implement a function to delete the entire tree if needed.    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, the insertBST function is used to insert nodes recursively into the BST, and the deleteBST function is used to delete nodes recursively from the BST. The in-order traversal is performed to see the sorted order of the BST before and after the deletion of a node.