Deletion in Binary Search Tree

Introduction

Binary Search Tree is also called Binary Sorted Tree. This is a variety of Binary Trees in Which All the elements which are Smaller than the Root element is at the Left, and all the elements which are greater than the Root element are at the Right.

How to Delete Nodes in a Binary Search Tree?

Recommended: Try the Problem yourself first before moving on to the solution

So, When we are dealing with the Deletion in Binary Search Tree few things are to be kept in mind what type of nodes are to be deleted and specific steps are to be followed for a specific type:

1- The node that we are Deleting in the Binary Search Tree is Leaf-Node:

Steps to be followed:

• Simply remove the node with the key value;

2-The node that we are Deleting in Binary Search Tree contains Only one child:

Steps to be followed:

• Make the non-Null Children {of the Root that is to be deleted} be root.

3-The node that we are Deleting in the Binary Search Tree contains Two children:

Steps to be followed:

• Find the Node to be deleted.
• After finding the node that is to be deleted then, consider the temporary root to be the node’s Right children.
• Now, find the smallest element of the Temporary root(i.e the leftmost Element).
• Now, Copy the data of this leftmost element to node data and Delete the leftMost element.
• Now, the deletion of the Leftmost element would be treated as Leaf Node Deletion.

Still getting confused, Check out the video below, which covers both the insertion and deletion of a node in BST along with visual representations and code.

Code in Java

public static BinaryTreeNode<Integer> helperr(BinaryTreeNode<Integer> root,int data){
        //base case
        if(root==null){
            return null;
        }
        //Step-1 :Find the node which is to be deleted
        if(root.data>data){
            root.left= helperr(root.left,data);
            return root;
        }else if(root.data<data){
            root.right= helperr(root.right,data);
            return root;
        }else{
            //Step-2 :once u have reached the node to be deleted
            //Step-3 :Identify the no of children to be Deleted
            //Case of leaf node simply Delete the Node
            if(root.left==null && root.right==null){
                return null;
            }
            //Case when only one children make the children as root
            if(root.left==null){
                return root.right;
            }
            if(root.right==null){
                return root.left;
            }
            // case 3 when both children is present 
            //find the leftmost children of (the right children of node i.e to be deleted) 
            BinaryTreeNode<Integer> temp=root.right;
            while(temp.left!=null){
                temp=temp.left;
            }
            root.data=temp.data;
            //make the leftmost child as root and Delete it
            root.right=helperr(root.right,temp.data);
            return root;
        }
    }

Code in C++

BinaryTreeNode<int>* deleteData(BinaryTreeNode<int>* root, int data)
    {
        //BASE CASE
        if(root == NULL)
            return NULL;
        //IF WE REACHED THE NODE TO BE DELETED
        if(data == root->data)
        {
            //CASE OF LEAF NODE
            if(!root->right && !root->left)
            {
                delete root;
                return NULL;
            }
            //CASE OF ONLY ONE CHILDREN OF THE NODE TO BE DELETED
            if(!root->right)
            {
                root = root->left;
                return root;
            }
            else if(!root->left)
            {
                root = root->right;
                return root;
            }
            else
            {
                //WHEN THE NODE CONTAINS BOTH THE CHILDREN
                BinaryTreeNode<int>* minNode = root->right;
                while(minNode->left!= NULL)
                {
                    minNode = minNode->left;
                }
                //PLACE THE LEFTMOST DATA OF NODE-RIGHT AS ROOT AND DELETE THE LEFTMOST CHILDREN OF ROOT,RIGHT
                int rightmin = minNode->data;
                root->data = rightmin;
                root->right = deleteData(root->right, rightmin);
                return root;
            }
            
            return root;
        }
        //ON THE WAY TO FIND THE NODE TO BE DELETED
        if(data < root->data && root->left)
        {
            root->left = deleteData(root->left, data);
            return root;
        }
        else if(data > root->data && root->right)
        {
            root->right = deleteData(root->right, data);
            return root;
        }
    }

Output

Time Complexity

The Worst-Case complexity of the code for the Deletion in the Binary Search Tree will be O(h), where “h” is the height of the Binary Search/Sorted Tree.
In the worst case, we have to travel from the root to the leaf node.

Check out this problem - Diameter Of Binary Tree