### Delete Node in a Binary Search Tree - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Data Structures >> Delete Node in a Binary Search Tree

In this post, we will learn how to Delete Node in a Binary Search Tree and will implement its solution in Java.

## Delete Node in a Binary Search Tree

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages. First, search for a node to remove. Second, If the node is found, delete the node.

Example:
root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3   6
/ \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2, null, null,7], shown in the following BST.

5
/ \
4   6
/     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

5
/ \
2   6
\   \
4   7

## Delete Node in a Binary Search Tree Java Solution

Approach 1

Using Recursion.

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return null;

//check left subtree
if(root.val > key){
root.left = deleteNode(root.left, key);
}

//check right subtree
else if(root.val < key){
root.right = deleteNode(root.right, key);
}

//if target equals to root
else{
//if left child is null then return right child
if(root.left == null){
return root.right;
}
else if(root.right == null){
return root.left;
}

//if target have two children
//found successor and swap with it
//then delete the node
TreeNode next = findNext(root.right);
root.val = next.val; //swap
root.right = deleteNode(root.right, root.val);
}
return root;
}

public TreeNode findNext(TreeNode root){
while(root.left != null){
root = root.left;
}
return root;
}
}
```

Approach 2

Iterative Solution.

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution
{
public TreeNode deleteNode(TreeNode root, int key)
{

TreeNode target = root, parent = null;

//Search Node
while (target != null && target.val != key)
{
parent = target;
if (key > target.val) target = target.right;
else target = target.left;
}

if (target == null) return root;  // not found

// Case 1 : No children
if(target.left==null && target.right==null)
{
if (parent == null) return null;
if(target==parent.left) parent.left=null;
else parent.right=null;
return root;
}

// Case 2 : One Child

// Case 2.1 : No right child
if(target.right==null)
{
if (parent == null) return target.left; //If target node is root itself
if (target == parent.left) parent.left = target.left;
else parent.right = target.left;
return root;
}

// Case 2.2 : No left child
if(target.left==null)
{
if (parent == null) return target.right;
if (target == parent.left) parent.left = target.right;
else parent.right = target.right;
return root;
}

// Case 3 : Both the child nodes present
{
/* Whenever we delete a node with two child then we replace that node```
`            with the leftmost element from the right subtree because to hold the `
```            property of BST
all the element to the right of the new node will be greater than it and all ```
```            the left ones will be lesser than it
*/
// Trace to the leftmost element in Right subtree
TreeNode prev = target, p = target.right;
while (p.left != null)
{
prev = p;
p = p.left;
}

target.val = p.val;
if (p == prev.left) prev.left = p.right;
else prev.right = p.right;
return root;
}
}
}
```

Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.