Binary search tree (BST)

• A Binary Search Tree (BST) is a special type of tree where the value of the left child node’s always less than the parent node and the value of the right child node is greater than the parent node.
• Commonly performed operations on binary search trees are searching, insertion, and deletion.
• Here, we see Delete operation in detail.

Delete Operation

• In a binary search tree, the Delete function is used to delete the specified node.
• But, delete a node from a binary search tree in such a way, that the property of the binary search tree doesn't violate.
• To achieve this there are three methods for deleting a node from a binary search tree are used.

Method - 1: Deletion of A Node Having No Child (Leaf Node)

Method - 2: Deletion of A Node Having Only One Child Node

Method - 3: Deletion of A Node Having Two Children Nodes

Method - 1: Deletion of A Node Having No Child (Leaf Node)

• It is the simplest method when deleting a node is the leaf node.
• In this, the leaf node with is replaced the NULL and simply free the allocated space.
• Consider the following example where leaf node with value = 30 is deleted from the BST:

Method - 2: Deletion of A Node Having Only One Child Node

• In this, replace the node that is going to be deleted with its only child node and then delete the child node, which now contains the value which is to be deleted.
• Replace it with the NULL and free the allocated space.
• Consider the following example where the node with one child node whose value = 25 is deleted from the BST:

Method - 3: Deletion of A Node Having Two Children Nodes

• It is a quite complex method case compared to the other two methods.
• In this, the node which is to be deleted is replaced with its in-order successor or predecessor recursively until the node to be deleted is replaced on the leaf of the tree.
• After this, replace the node with NULL and free the allocated space. Consider the following example where the node with two child nodes whose value = 60 is deleted from the BST:

In-order Traversal Sequence of the following Tree is 15, 25, 30, 60, 65, 75, 85, 90, 95.

A node with two children can be deleted from the BST in the following two ways:

Way 1:

• Visit the right subtree of the deleting node.
• Take the least value node called the in-order successor node.
• Replace the deleting node with its in-order successor node.
• In this way take the node with value 65 which is the least valued in-order successor node of node 60 that is to be deleted.

Way 2:

• Visit the left subtree of the deleting node.
• Take the greatest value node called the in-order predecessor node.
• Replace the deleting node with its in-order predecessor node.
• In this way take the node with value 30 which is the greatest valued in-order predecessor node of the node 60 that is to be deleted.

Function For Deletion in BST

Each of the methods mentioned above can be implemented as follows:

// Function to delete a node from a BST    
void deletion(Node*& root, int item)  
{  
    // pointer to store the parent of the current node
    Node* parent = NULL;  

    // start with the root node
    Node* cur = root;  

    // return if the key is not found in the tree
    search(cur, item, parent);  
    if (cur == NULL)  
        return; 

    // Method 1: when node to be deleted has no children,means it is a leaf node  
    if (cur->left == NULL && cur->right == NULL)  
    {  
        // if the node to be deleted is not a root node, then set its
        // parent left/right child to null
        if (cur != root)  
        {  
            if (parent->left == cur)  
                parent->left = NULL;  
            else  
                parent->right = NULL;  
        }  
        // if the tree has only a root node, set it to null
        else  
            root = NULL;  

        // deallocate the memory  
        free(cur);               // or delete curr;
    }
    // Method 3: when node to be deleted has two children  
    else if (cur->left && cur->right)  
    {  
        // find its inorder successor node
        Node* succ  = findMinimum(cur- >right); 

        // find its inorder successor node  
        int val = succ->data; 

         // recursively delete the successor. Note that the successor
        // will have at most one child (right child)
        deletion(root, succ->data);  

        // copy value of the successor to the current node  
        cur->data = val;  
    }  
    // Method 2: when node to be deleted has only one child  
    else  
    {  
        // choose a child node
        Node* child = (cur->left)? Cur- >left: cur->right;  

        // if the node to be deleted is not a root node, set its parent
        // to its child  
        if (cur != root)  
        {  
            if (cur == parent->left)  
                parent->left = child;  
            else  
                parent->right = child;  
        }  

        // if the node to be deleted is a root node, then set the root to the child 
        else  
            root = child;  

        // deallocate the memory
        free(cur);  
    }  
}  

// Helper function to find minimum value node in the subtree rooted at `curr` 
Node* findMinimum(Node* cur)  
{  
    while(cur->left != NULL) {  
        cur = cur->left;  
    }  
    return cur;  
}