### How to delete a Node in Binary Search Tree?

There are 3 cases that need to be considered while deleting a node from Binary Search Tree.

1. Node to delete

**has no children**that is no left child and no right child present. Case 1 in below image.

2. Node to delete

**has only one child**either left child or right child present. Case 2 in below image.

3. Node to delete

**has both child**that is left child and right child present. Case 3 in below image.

**Case 1:**

For case 1, it is very much straightforward,

**1.**Search for the node that need to be deleted.

**2.**Node to be deleted is either on left side or on right side of its parent node.

**3.**If node to be deleted is on left side of its parent node then mark Left side of parent node to null.

Eg: parent.setLeft(null);

**4.**If node to be deleted is on right side of its parent node then mark Right side of parent node

to null. Eg: parent.setRight(null);

**Case 2:**

For case 2, it is very much straightforward,

**1.**Search for the node that need to be deleted.

**2.**Node to be deleted is either on left side or on right side of its parent node.

**3.**Node to be deleted has only child present that can be on left side or right side.

**4.**If node to be deleted has left child present,

then directly connect its parent node to left child node of node to be deleted.

Eg: parent.setLeft(child.getLeft());

**5.**If node to be deleted has right child present,

then directly connect its parent node to right child node of node to be deleted.

Eg: parent.setRight(child.getRight());

**6.**In this way node to be deleted will be removed from the Tree and parent node

will be directly connected to child node of node to be deleted.

**Case 3:**

For case 3, it is little bit tricky

**1.**Search for the node that need to be deleted.

**2.**Now, instead of deleting the node, we will replace the data of node to be deleted

with the data that will be best fit in that place.

**3.**

**Which data will be best fit?**Search the data from the sub tree of node to be deleted and

find the node whose data when placed at the place of node to be deleted will

**keep the Binary Search Tree property(key in each node must be greater**

**than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree) intact.**

**4.**Find minimum element from the right sub tree of node to be deleted or

find maximum element from the left sub tree of node to be deleted and

copy that Node data to the data of node to be deleted.

**5.**Delete the node which we found the best fit in step 5.

### Java Program to delete a Node from Binary Search Tree.

package tree; public class DeleteNodeInBinarySearchTree { private Node rootNode; public static void main(String[] args) { new DeleteNodeInBinarySearchTree(); } public DeleteNodeInBinarySearchTree(){ addNode(rootNode, 10); addNode(rootNode, 5); addNode(rootNode, 20); addNode(rootNode, 3); addNode(rootNode, 8); addNode(rootNode, 18); addNode(rootNode, 25); addNode(rootNode, 7); addNode(rootNode, 23); addNode(rootNode, 30); addNode(rootNode, 21); addNode(rootNode, 24); printTreeInOrder(rootNode); rootNode = deleteNode(rootNode,20); printTreeInOrder(rootNode); } private Node deleteNode(Node rootNode, int data) { if(rootNode==null){ return null; } if(data==rootNode.getData()){ if(rootNode.getLeft()!=null && rootNode.getRight()!=null){ //Find Minimum from Right Tree OR find Maximum from Left Tree. Node minNode = getHighestNodeFromRight(rootNode.getRight()); rootNode.setData(minNode.getData()); rootNode.setRight(deleteNode(rootNode.getRight(), minNode.getData())); System.out.println(minNode); }else if(rootNode.getLeft()==null){ return rootNode.getRight(); }else{ return rootNode.getLeft(); } }else if(data>rootNode.getData()){ rootNode.setRight(deleteNode(rootNode.getRight(), data)); }else{ rootNode.setLeft(deleteNode(rootNode.getLeft(), data)); } return rootNode; } public Node getHighestNodeFromRight(Node node){ if(node.getLeft()==null){ return node; }else{ Node n = getHighestNodeFromRight(node.getLeft()); return n; } } private void printTreeInOrder(Node rootNode){ if(rootNode==null) return; printTreeInOrder(rootNode.getLeft()); System.out.print(rootNode.getData() + " "); printTreeInOrder(rootNode.getRight()); } private void addNode(Node rootNode, int data){ if(rootNode==null){ this.rootNode=new Node(data); }else{ addNodeInProperPlace(rootNode, data); } } private void addNodeInProperPlace(Node rootNode, int data){ if(data>rootNode.getData()){ if(rootNode.getRight()!=null){ addNode(rootNode.getRight(), data); }else{ Node temp1 = new Node(data); rootNode.setRight(temp1); } }else{ if(rootNode.getLeft()!=null){ addNode(rootNode.getLeft(), data); }else{ Node temp1 = new Node(data); rootNode.setLeft(temp1); } } } }

### You may also like to see

#### Connect nodes at same level in a Binary Tree

#### Find diameter of Binary Tree.

#### Convert Sorted Array to Balanced Binary Search Tree

#### Serialize and Deserialize a Binary Tree

#### Multithreading Interview question-Answers

**Enjoy !!!!**

**If you find any issue in post or face any error while implementing, Please comment.**

## Post a Comment