Last updated on October 5th, 2024 at 08:53 pm

Here, We see Delete Node in a BST LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Delete Node in a BST LeetCode Solution

Problem Statement

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:

1. Search for a node to remove.
2. If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: 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 above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it’s also accepted.

Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:
Input: root = [], key = 0
Output: []

1. Delete Node in a BST LeetCode Solution C++

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root) 
            if(key < root->val) root->left = deleteNode(root->left, key);
            else if(key > root->val) root->right = deleteNode(root->right, key);       
            else{
                if(!root->left && !root->right) return NULL;
                if (!root->left || !root->right)
                    return root->left ? root->left : root->right; 
                TreeNode* temp = root->left;
                while(temp->right != NULL) temp = temp->right;
                root->val = temp->val;
                root->left = deleteNode(root->left, temp->val);
            }
        return root;
    }   
};

2. Delete Node in a BST LeetCode Solution Java

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        if(key<root.val){                            
            root.left = deleteNode(root.left,key);
            return root;
        }
        else if(key>root.val){
            root.right = deleteNode(root.right,key);
            return root;
        }
        else{
            if(root.left==null){
                return root.right;
            }
            else if(root.right==null){
                return root.left;
            }
            else{
                TreeNode min = root.right;
                while(min.left!=null){
                    min = min.left;
                }
                root.val = min.val;
                root.right = deleteNode(root.right,min.val);
                return root;
            }
        }
    }
}

3. Delete Node in a BST LeetCode Solution JavaScript

var deleteNode = function(root, key) {
    if (null === root) { return null; }
    if (root.val === key) {
        if (null === root.left && null === root.right) { return null; }
        if (null !== root.left && null !== root.right) {
            let curr = root.right;
            while (curr.left) { curr = curr.left; }
            curr.left = root.left;
            return root.right;
        }
        if (null === root.left) { return root.right; }
        if (null === root.right) { return root.left; }
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
};

4. Delete Node in a BST LeetCode Solution Python

class Solution(object):
    def deleteNode(self, root, key):
        if not root: return None
        if root.val == key:
            if root.left:
                left_right_most = root.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                left_right_most.right = root.right
                return root.left
            else:
                return root.right
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
        return root