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

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