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

- Insert Node into a Binary Search Tree
- Introduction to Binary Search Tree
- Introduction to Binary Tree
- Binary Tree Postorder Traversal
- Introduction to Strings

## Comments

## Post a Comment