Leetcode 450. Delete Node in a BST

Problem

You are given the root of a binary search tree (BST) and an integer key representing the value of a node to delete. Remove the node containing this key from the BST while maintaining the binary search tree property.

After deletion, the resulting tree must still be a valid BST where all nodes in the left subtree are less than the parent, and all nodes in the right subtree are greater than the parent.

Return the root node of the modified BST. If the key is not found in the tree, return the original tree unchanged.

Requirements

1. Maintain the BST property after deletion
2. Handle all three deletion cases: leaf nodes, nodes with one child, and nodes with two children
3. Return the root of the modified tree (which may be different from the original root)
4. If the key doesn't exist in the tree, return the tree unchanged

Constraints

• The number of nodes in the tree is in the range [0, 104]
• -105 ≤= Node.val ≤= 105
• Each node has a unique value
• -105 ≤= key ≤= 105
• Time complexity should be O(h) where h is the height of the tree
• Space complexity should be O(h) for the recursive call stack

Examples

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: We remove node 3. Since it has two children, we replace it with its inorder successor (smallest node in right subtree), which is 4.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: Key 0 doesn't exist in the tree, so no changes are made.

Example 3:

Input: root = [], key = 0 Output: [] Explanation: The tree is empty, so we return null.

Example 4:

Input: root = [5,3,6,2,4,null,7], key = 5 Output: [6,3,7,2,4] Explanation: We remove the root node 5 and replace it with its inorder successor 6.

Hint 1: BST Search Use the BST property to efficiently locate the node to delete. Compare the key with the current node's value to decide whether to search left or right.

Hint 2: Deletion Cases There are three cases to handle:

1. Node is a leaf (no children): simply remove it
2. Node has one child: replace the node with its child
3. Node has two children: find the inorder successor (smallest node in right subtree) or inorder predecessor (largest node in left subtree), replace the node's value with it, and then delete that successor/predecessor

Hint 3: Inorder Successor For a node with two children, the inorder successor is found by going one step right, then going as far left as possible. This gives you the smallest value that's still larger than the current node.

Full Solution `` Approach:

The solution uses recursion to traverse the BST and locate the target node:

1. Search Phase: Navigate through the tree using BST properties (go left if key is smaller, right if larger)

2. Deletion Cases:

   • Leaf or One Child: If the node has no left child, return the right child (which could be None). If no right child, return the left child.
   • Two Children: Find the inorder successor (smallest value in the right subtree), copy its value to the current node, then recursively delete the successor from the right subtree.

3. Return Updated Root: Each recursive call returns the new root of its subtree, allowing parent nodes to update their child pointers.

Time Complexity: O(h) where h is the height of the tree. In the worst case (skewed tree), this is O(n). In a balanced tree, it's O(log n).

Space Complexity: O(h) for the recursive call stack.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    # Base case: empty tree or key not found
    if not root:
        return None
    
    # Search for the node to delete
    if key < root.val:
        # Key is in the left subtree
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        # Key is in the right subtree
        root.right = deleteNode(root.right, key)
    else:
        # Found the node to delete
        
        # Case 1: Node is a leaf or has only one child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        
        # Case 2: Node has two children
        # Find the inorder successor (smallest node in right subtree)
        successor = find_min(root.right)
        
        # Replace current node's value with successor's value
        root.val = successor.val
        
        # Delete the successor from the right subtree
        root.right = deleteNode(root.right, successor.val)
    
    return root

def find_min(node: TreeNode) -> TreeNode:
    """Find the minimum value node in a subtree."""
    while node.left:
        node = node.left
    return node