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.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala