# 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.

## There are three possible cases in deletion :-

##### 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.

##### 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.

##### 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.

## CODE FOR DELETION IN BINARY SEARCH TREE

`//Deletion in BinarySearch Treeimport 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 Tree30 50 60 70 75 80 95Inorder Traversal After deleting a Node 6030 50 70 75 80 95Inorder Traversal After deleting a Node 5030 70 75 80 95Inorder Traversal After deleting a Node 8030 70 75 95`

O(n)

O(h)