In the post Binary Tree Implementation in Java - Insertion, Traversal And Search we have already seen Binary search tree implementation in Java for insertion, search and traversal operations. In this post we’ll see how to delete a node from Binary search tree in Java. Since deletion of a node from binary search tree is considered the most complex operation, having many scenarios so it is taken up as a separate post.
Deleting a node in binary search tree
Deleting a node consists of two operations-
- Search for the node that has to be deleted.
- Delete the node once it is found.
When the node is found and you are going to delete it you need to consider the following three cases.
- The node that has to be deleted is a leaf node (has no children).
- The node that has to be deleted has one child.
- The node that has to be deleted has two children.
Based on these cases logic for deleting a node differs so we’ll go through these cases for deleting a node in binary search tree one by one.
Once all the scenarios are explained we'll see the full Java program for binary search tree node deletion using both-
Deleting a node in binary search tree - Node has no children
If node to be deleted is a leaf node that is the simplest binary search tree node deletion case. In this case left or right reference of the parent node (parent of the node that has to be deleted) is set to null based on whether the deleted node is the left child or the right child.
If node to be deleted is current and its parent is called parent then the code for deleting a leaf node can be written as-
// if root node is to be deleted
if(current == root){
root = null;
}
// left child
else if(isLeftChild){
parent.left = null;
}
// right child
else{
parent.right = null;
}
Deleting a node in binary search tree - Node has one child
If a node to be deleted has one child then there are two scenarios-
If deleted node has a left child then that child becomes the left child of the parent if deleted node is the left child otherwise child of the deleted node becomes the right child of the parent if deleted node is the right child.
If deleted node has a right child then that child becomes the left child of the parent if deleted node is the left child otherwise child of the deleted node becomes the right child of the parent if deleted node is the right child.
If node to be deleted is current and its parent is parent then the code for deleting a node with one child can be written as-
// if node to be deleted has right child
if(current.left == null){
// if root node is to be deleted
if(current == root){
root = current.right;
}
// if deleted node is left child
else if(isLeftChild){
parent.left = current.right;
}
// if deleted node is right child
else{
parent.right = current.right;
}
}
//if node to be deleted has left child
else if(current.right == null){
if(current == root){
root = current.left;
}
// if deleted node is left child
else if(isLeftChild){
parent.left = current.left;
}
// if deleted node is right child
else{
parent.right = current.left;
}
}
Deleting a node in binary search tree - Node has two children
Case when node to be deleted has two children is the most complex out of the three cases.
To delete a node with two children in binary search tree you need to find the inorder successor of the node to be deleted. In-order successor is the next highest node and to find it you need to go to the right child of the deleted node and from there traverse the left subtree until null is encountered, that last node is the in-order successor of the node to be deleted.
Once the in-order successor is found there are two scenarios-
- In-order successor is the right child of the node to be deleted, as there is no left subtree to traverse.
- In-order successor is a node in the left subtree which you start traversing after going to the right child of the deleted node.
Let’s see both of these scenarios, when deleting a node with two children in binary search tree, in detail.
In-order successor right child of the node to be deleted
If right child of the node to be deleted has no left child then that right child itself is the in-order successor of the node to be deleted and it has to take the place of the deleted node.
- Parent of the node to be deleted should start referencing to the in-order successor.
- Left child of the node to be deleted should become the left child of the successor.
If node to be deleted is current, its parent is parent and in-order successor is called successor then the pseudo code for deleting a node in this case can be written as-
// Find successor
Node successor = findSuccessor(deleteNode)
// if node to be deleted is left child
if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
In-order successor is in the left subtree
If the in-order successor is found in the left subtree of the right child of the node to be deleted then the following steps are required for deleting a node.
- Successor’s right child should become the left child of the successor’s parent.
- Right child of the node to be deleted should become the right child of the successor.
- Left child of the node to be deleted becomes the left child of the successor.
- Parent of the node to be deleted should start referencing in-order successor of the node to be deleted.
If node to be deleted is current, its parent is parent, in-order successor is called successor and its parent is successorParent then the code for deleting a node in this case can be written as-
// Find successor
Node successor = findSuccessor(deleteNode)
// if node to be deleted is left child
if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successorParent.left = successor.right;
successor.right = current.right;
successor.left = current.left;
Deleting a node in binary search tree Java implementation – Iterative
Now when we have a good understanding of all the scenarios while deleting a node in BST we’ll have the Java implementation for deleting a node in BST. It can be written as both iterative method and recursive method. Both approaches are shown here.
public class BinaryTree {
// first node
private Node root;
BinaryTree(){
root = null;
}
// Class representing tree nodes
static class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
public void displayData(){
System.out.print(value + " ");
}
}
public void insert(int i){
root = insert(root, i);
}
//Inserting node - recursive method
public Node insert(Node node, int value){
if(node == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < node.value){
node.left = insert(node.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > node.value){
node.right = insert(node.right, value);
}
return node;
}
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
public boolean delete(int value){
Node current = root;
Node parent = root;
boolean isLeftChild = false;
while(current.value != value){
parent = current;
if(value < current.value){
// Move to the left if searched value is less
current = current.left;
isLeftChild = true;
}
else{
// Move to the right if searched value is >=
current = current.right;
isLeftChild = false;
}
if(current == null){
return false;
}
}
// if reached here means node to be deleted is found
// Leaf node deletion case
if(current.left == null && current.right == null){
System.out.println("Leaf node deletion case");
// if root node is to be deleted
if(current == root){
root = null;
}
// left child
else if(isLeftChild){
parent.left = null;
}
// right child
else{
parent.right = null;
}
}
// Node to be deleted has one child case
// Node to be deleted has right child
else if(current.left == null){
System.out.println("One right child deletion case");
// if root node is to be deleted
if(current == root){
root = current.right;
}
// if deleted node is left child
else if(isLeftChild){
parent.left = current.right;
}
// if deleted node is right child
else{
parent.right = current.right;
}
}
// Node to be deleted has left child
else if(current.right == null){
System.out.println("One left child deletion case");
if(current == root){
root = current.left;
}
// if deleted node is left child
else if(isLeftChild){
parent.left = current.left;
}
// if deleted node is right child
else{
parent.right = current.left;
}
}
// Node to be deleted has two children case
else{
System.out.println("Two children deletion case");
// find in-order successor of the node to be deleted
Node successor = findSuccessor(current);
if(current == root){
root = successor;
}
// if deleted node is left child
else if(isLeftChild){
parent.left = successor;
}
// if deleted node is right child
else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}
// Method to find the in-order successor of the deleted node
private Node findSuccessor(Node node){
Node successor = node;
Node successorParent = node;
// Start from the right child of the node to be deleted
Node current = node.right;
while(current != null){
successorParent = successor;
successor = current;
current = current.left;
}
// When In-order successor is in the left subtree
// perform two ref changes here as we have
// access to successorParent
if(successor != node.right){
successorParent.left = successor.right;
// applicable only when successor is not right child
// so doing here
successor.right = node.right;
}
return successor;
}
public static void main(String[] args) {
BinaryTree bst = new BinaryTree();
bst.insert(50);
bst.insert(70);
bst.insert(30);
bst.insert(15);
bst.insert(35);
bst.insert(7);
bst.insert(22);
bst.insert(31);
System.out.println("Inorder traversal of binary tree");
bst.inOrder(bst.root);
System.out.println();
boolean deleteFlag = bst.delete(35);
if(deleteFlag)
System.out.println("Node successfully deleted");
System.out.println("Inorder traversal after deletion");
bst.inOrder(bst.root);
System.out.println();
}
}
Deleting a node in binary search tree Java implementation – Recursive
Following method shows the recursive Java implementation for deleting a node in binary search tree.
public Node deleteNode_recur(Node node, int value){
if(node == null)
return null;
if(value < node.value){
node.left = deleteNode_recur(node.left, value);
}else if (value > node.value){
node.right = deleteNode_recur(node.right, value);
}else{
// Leaf node deletion case
if(node.left == null && node.right == null){
System.out.println("Leaf node deletion case");
node = null;
}
// Node to be deleted has one child case
// Node to be deleted has right child
else if(node.left == null){
System.out.println("Having One right child deletion case");
node = node.right;
}
// Node to be deleted has left child
else if(node.right == null){
System.out.println("Having One left child deletion case");
node = node.left;
}
// Node to be deleted has two children case
else{
System.out.println("Two children deletion case");
Node successor = findSuccessor_recur(node.right);
// Copy the value
node.value = successor.value;
// delete successor node instead
node.right = deleteNode_recur(node.right, successor.value);
}
}
return node;
}
private Node findSuccessor_recur(Node node){
if(node.left == null)
return node;
else
return findSuccessor_recur(node.left);
}
Which can then be executed using following method call.
newRoot = bst.deleteNode_recur(bst.root, 15); bst.inOrder(newRoot);
That's all for this topic Java Program to Delete a Node From Binary Search Tree (BST). If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
Hi, in the full code for iterative approach, deletion of node with 2 children does not handle the 2nd case when successor is on the left subtree of the deleted node's right child. I believe you left that part out.
ReplyDeletenvm you handled it in findsuccessor function... thank you for the very informative tutorial
ReplyDeleteI had problem with deleting Node with 2 children and your guide helped me a lot. Thank you
ReplyDelete