Deletion In Binary Search Tree In Java

Deletion In Binary Search Tree

Binary Search Tree is a rooted binary tree whose internal nodes each a key greater than all the keys in the node’s left subtree and less than those in it’s right subtree. Delete function is used to delete the specified node from binary search tree. In this article we will perform deletion in binary search tree.

Deletion in Binary Search Tree

There are three possible cases in deletion :-

  1. Deleting a node with no children .
  2. Deleting a node with two children. 
  3. Deleting a node with no child.
Case 1: Deleting a node with no children :-

If the node to be deleted from the tree has no child nodes, the node is simple deleted from the tree since it is a leaf node.

Deleting a Node with no children
Case 2: Deleting a node with two children :-

we first find the inorder predecessor of the node and replace the target node with the inorder predecessor.

Deleting a node with two children
Case 3: Deleting a node with one child :-

If the node to be deleted has a single child node, the target node is replaced from its child node and then the target node is simply deleted.

Deleting a Node with one child

CODE FOR DELETION IN BINARY SEARCH TREE

//Deletion in BinarySearch Tree
import java.util.*;
/*Representing a Node of a Binary Search Tree*/
class Node
{
   int value;
   Node left,right;    
   //constructor
   Node(int value)
   {
       this.value=value;
       left=null;
       right=null;
   }
}
class BSTDeletion
{
   Node root;  //Root of a Binary Search Tree
   public BSTDeletion()
   {
        root=null;
   }
   /*Inorder Traversal of a Binary Tree */
   public void inorder(Node ptr)
   {
       if(ptr==null)
           return;
       inorder(ptr.left);
       System.out.print(ptr.value+" ");
       inorder(ptr.right);
   }
   public void delete(int value)
   {
       root=deleteNode(root,value); //calling deleteNode() method
   }
    public  Node  deleteNode(Node ptr,int value)
   {
       if(ptr==null) 
       return ptr;
       if(value<ptr.value)  //if value is less than current value
           ptr.left=deleteNode(ptr.left,value);
       else if(value>ptr.value) //if value if greater than current value
           ptr.right=deleteNode(ptr.right,value);
       else 
       {
       //if node having max one child
       if(ptr.left==null)    
           return ptr.right;
       else if(ptr.right==null)
           return ptr.left;
       // if node having two children then get the inorder predecessor of node
       ptr.value=minimumValue(ptr.left);
       //delete the inorder predecessor
        ptr.left=deleteNode(ptr.left,ptr.value);  
        }
       return ptr;
   }
   //get minimum element in binary search tree
   public int minimumValue(Node ptr)
   {
       int min;
       for(min=ptr.value;ptr.right!=null;ptr=ptr.right)
       min=ptr.right.value;
       return min; 
   }
   public static void main(String[] args)
   {
       //Creating Binary Search Tree
       BSTDeletion tree=new BSTDeletion();
       tree.root=new Node(70);
       tree.root.left=new Node(50);
       tree.root.right=new Node(80);
       tree.root.left.left=new Node(30);
       tree.root.left.right=new Node(60);
       tree.root.right.left=new Node(75);
       tree.root.right.right=new Node(95);
       System.out.println("Inorder Traversal of a Binary Search Tree");
       tree.inorder(tree.root); 
       tree.delete(60);
       System.out.println();
       System.out.println("Inorder Traversal After deleting a Node 60");
       tree.inorder(tree.root); 
       tree.delete(50);
       System.out.println();
       System.out.println("Inorder Traversal After deleting a Node 50");
       tree.inorder(tree.root);
       tree.delete(80);
       System.out.println();
       System.out.println("Inorder Traversal After deleting a Node 80"); 
       tree.inorder(tree.root); 
   } 
}

Output:

Inorder Traversal of a Binary Search Tree
30 50 60 70 75 80 95
Inorder Traversal After deleting a Node 60
30 50 70 75 80 95
Inorder Traversal After deleting a Node 50
30 70 75 80 95
Inorder Traversal After deleting a Node 80
30 70 75 95

Time And Space Complexity to Delete a Node in Binary Search Tree

Time Complexity

O(n)

Space Complexity 

O(h)