Do you think IIT Guwahati certified course can help you in your career?
Introduction
Binary Search Treeis 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.
In this blog, we will learn about deletion in binary search tree (BST). We will learn about how to delete nodes in binary search tree and its implementation in java,
What is Deletion in a Binary Search Tree (BST)?
Deletion in a Binary Search Tree (BST) is the process of removing a node from the tree while maintaining its properties. There are three cases to consider: deleting a leaf node, a node with one child, or a node with two children. For a leaf node, simply remove it. For a node with one child, replace it with its child. For a node with two children, find the inorder successor (the smallest node in the right subtree) or predecessor (the largest node in the left subtree), replace the node's value with the successor's or predecessor's value, and then delete the successor or predecessor.
How to Delete Nodes in a Binary Search Tree?
Recommended: Try theProblemyourself 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;
}
}
You can also try this code with Online Java Compiler
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;
}
}
You can also try this code with Online C++ Compiler
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.
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.
84+ registered