450. Delete Node in a BST

Description

The problem involves deleting a node with a specified key from a binary search tree (BST). The task is to find the node with the given key and remove it from the tree while maintaining the properties of a BST. The key considerations include handling cases where the node to be deleted has no children, one child, or two children.

Intuition

When deleting a node from a BST, the structure and properties of the tree must be preserved. The complexity arises when the node to be deleted has two children. The most intuitive solution involves finding either the minimum value in the right subtree or the maximum value in the left subtree (inorder successor or predecessor) to replace the deleted node.

Approach

1. Traverse the Tree: Begin by locating the node to be deleted by traversing the tree from the root.
2. Handle Deletion Cases: - Leaf Node: If the node has no children, simply remove it. - Single Child: If the node has one child, replace the node with its child. - Two Children: If the node has two children, find the minimum value in the right subtree (inorder successor), replace the node's value with this minimum value, and recursively delete the inorder successor.
3. Recursive Deletion: Implement the solution recursively, adjusting pointers to maintain the BST structure.

Complexity

Time Complexity:

The time complexity is O(h), where h is the height of the tree. In the worst case, this could be O(n) for a skewed tree.

Space Complexity:

The space complexity is O(h) due to the recursive call stack, which in the worst case could also be O(n).

Code

C++

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;

        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 nullptr;
            if (!root->left) return root->right;
            if (!root->right) return root->left;

            root->val = findMin(root->right);
            root->right = deleteNode(root->right, root->val);
        }

        return root;
    }

private:
    int findMin(TreeNode* root) {
        while (root->left) {
            root = root->left;
        }
        return root->val;
    }
};

Python

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left and not root.right:
                return None
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            
            root.val = self.findMin(root.right)
            root.right = self.deleteNode(root.right, root.val)
        
        return root

    def findMin(self, root: TreeNode) -> int:
        while root.left:
            root = root.left
        return root.val

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);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null && root.right == null) return null;
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            root.val = findMin(root.right);
            root.right = deleteNode(root.right, root.val);
        }

        return root;
    }

    private int findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }
}

JavaScript

var deleteNode = function (root, key) {

    function removeNode(root, key) {

        if (root == null) return null;
        if (key < root.val) {
            root.left = removeNode(root.left, key);
        }

        else if (key > root.val) {
            root.right = removeNode(root.right, key);
        } 
        else {
            if (!root.left && !root.right) return null;
            if (!root.left) return root.right;
            if (!root.right) return root.left;
            root.val = min(root.right);
            root.right = removeNode(root.right, root.val);
        }

        return root;
    }
    return removeNode(root, key)
};

function min(root) {
    if (!root.left) return root.val;
    return min(root.left);
}