450. Delete Node in a BST Medium

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: []

Approach

Input: The root node of a Binary Search Tree (BST) root and a value key

Output: Delete the node corresponding to key and ensure the properties of the binary search tree are maintained, returning the reference to the potentially updated root node

This problem is suitable to be solved using the properties of Binary Search Tree (BST) combined with Bottom-up DFS.

1. Search for a node

• Same as regular BST search:
• If key < root.val → Search in the left subtree
• If key > root.val → Search in the right subtree
• If key == root.val → Found it, enter deletion logic

2. Delete node

• The deletion logic is divided into different cases:

• The target node has no child nodes (leaf node)

• Return None directly, simply deleting it.

• There is only one child node (left or right)

• Return that non-empty child node, letting it "replace" the current node.

• There are two child nodes (most complex case)

• Find its inorder successor (minimum node in the right subtree) or inorder predecessor (maximum node in the left subtree);

• Replace the current node with its value;

• Then recursively delete that successor/predecessor node in the corresponding subtree.

This not only ensures the ordering of the BST, but also completes the deletion.

Implementation

python

class Solution:
    def findmin(self, root):
        # Find the minimum value node, which is the leftmost node in the left subtree
        while root.left:
            root = root.left
        return root
    
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        # If the tree is empty, return directly
        if not root:
            return root
        
        # If the key is less than the current node's value, recursively search in the left subtree
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        
        # If the key is greater than the current node's value, recursively search in the right subtree
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        
        # Found the node to be deleted
        else:
            # If the node is a leaf node, delete it directly
            if not root.left and not root.right:
                root = None
            
            # If there is only a right subtree, use the right subtree as replacement
            elif not root.left:
                root = root.right
            
            # If there is only a left subtree, use the left subtree as replacement
            elif not root.right:
                root = root.left
            
            # If there are two child nodes
            else:
                # Find the minimum node in the right subtree to replace the current node
                temp = self.findmin(root.right)
                root.val = temp.val
                # Recursively delete the minimum node from the right subtree
                root.right = self.deleteNode(root.right, temp.val)
        
        return root

javascript

var deleteNode = function(root, key) {
    if (!root) return root;

    if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else {
        if (!root.left) return root.right;
        if (!root.right) return root.left;

        const succ = _miniNode(root.right, key);
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }

    return root;
};

function _miniNode(node) {
    while (node.left) {
        node = node.left
    }

    return node;
}

Complexity Analysis

• Time Complexity: O(h)
• Space Complexity: O(h)

Links

450. Delete Node in a BST (English)

450. 删除二叉搜索树中的节点 (Chinese)