Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
How to Delete Nodes in a Binary Search Tree?
2.1.
Code in Java
2.2.
Code in C++
2.3.
Time Complexity
3.
Frequently Asked Questions
3.1.
What is a Binary Tree?
3.2.
What are Binary Search Trees?
3.3.
Why are Binary Search Trees used?
3.4.
What are the different scenarios that take place when deleting nodes from a Binary Search Tree?
3.5.
What are the time and space complexities of making deletions in a binary search tree?
4.
Conclusion
4.1.
Recommended Reading
Last Updated: Mar 27, 2024
Medium

Deletion in Binary Search Tree

Author Souhard Swami
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Binary Search Tree

 

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;
Delete 20



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.
Delete 30


 

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.
Delete 50


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

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.

BST

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Binary Tree?

A variety of Tree that has a maximum of two child Nodes is a Binary tree.

What are Binary Search Trees?

It is a variety of Binary trees in which the root node is greater than the left child but less than the right child node.

Why are Binary Search Trees used?

It is beneficial in many scenarios where we have to compare the sorted data then it can be used.

What are the different scenarios that take place when deleting nodes from a Binary Search Tree?

There are three scenarios :
Deletion of leaf node
Deletion of a node with only one child
Deletion of a node with two child

What are the time and space complexities of making deletions in a binary search tree?

Time complexity is O(h)

Conclusion

Deletion in Binary Search Tree can be based on the various scenarios; if the Node to be deleted is left Node, then Deletion in Binary Search Tree can be done by simply deleting it. If the Node to be deleted is an intermediate node, and contains only one child, then Deletion in the Binary Search Tree can be done by making the child node the root node. If the Deletion in Binary Search Tree is to be done for the Node containing Two children, then the leftmost Element of the right children and make the root node. And then delete the leftmost Node. In this blog, we discussed all the above-mentioned approaches in detail along with their implementation.

Recommended Reading

Recommended problems -

 

Also, check out some of our Guided Paths on topics such as Data Structures and Algorithms along with some Contests and Interview Experiences only on Coding Ninjas Studio.

Cheers!

Previous article
Insertion in Threaded Binary Search Tree
Next article
Binary Search Tree | Iterative Delete
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass