Wednesday, March 13, 2019

Java Program to Delete a Node From Binary Search Tree (BST)

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-

  1. Search for the node that has to be deleted.
  2. 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.

  1. The node that has to be deleted is a leaf node (has no children).
  2. The node that has to be deleted has one child.
  3. 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.

deleting node in BST

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.

binary search tree node deletion java

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-

  1. In-order successor is the right child of the node to be deleted, as there is no left subtree to traverse.
  2. 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.

  1. Parent of the node to be deleted should start referencing to the in-order successor.
  2. Left child of the node to be deleted should become the left child of the successor.
delete node in BST

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.

  1. Successor’s right child should become the left child of the successor’s parent.
  2. Right child of the node to be deleted should become the right child of the successor.
  3. Left child of the node to be deleted becomes the left child of the successor.
  4. 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

  1. Sorted Linked List In Java
  2. Doubly Linked List Implementation Java Program
  3. Radix Sort Program in Java
  4. Find The First Repeated Character in a String
  5. Displaying Prime Numbers - Java Program

You may also like-

  1. How to Create PDF in Java Using OpenPDF
  2. How to Create Deadlock in Java
  3. How to Format Time in AM-PM Format - Java Program
  4. How to Read Input From Console in Java
  5. Heap Memory Allocation in Java
  6. Nested Class And Inner Class in Java
  7. Java Exception Handling Interview Questions And Answers
  8. Spring Expression Language (SpEL) With Examples