Delete Node in a BST

Problem in plain words

Given the root of a binary search tree and a key, remove the node holding that key (if it exists) and return the root of the resulting tree. The result must still be a valid BST. If the key is not present, return the tree unchanged.

Example: BST 8 with children 4 and 12, where 12 has children 10 and 14. Deleting 12 can produce 8 with children 4 and 14, where 14 now has left child 10. Other valid shapes are also accepted.

Intuition

First find the node with a normal BST search. Then there are three cases. A leaf can simply disappear. A node with one child can be replaced by that child, because the whole child subtree already fits in the node's position. A node with two children needs a replacement value that is larger than everything on the left and smaller than everything on the right — the in-order successor (the smallest value in the right subtree) is exactly that. Copy the successor's value into the node, then delete the successor from the right subtree; the successor has no left child, so that second deletion is an easy case.

Approach

1. If the node is null, return null (key not found).
2. If key < node.val, set node.left = deleteNode(node.left, key); if larger, do the same on the right. Return node.
3. If key == node.val and the node has no left child, return its right child (this also covers leaves).
4. If it has no right child, return its left child.
5. Otherwise find the leftmost node of the right subtree, copy its value into node, and set node.right = deleteNode(node.right, successorValue). Return node.

Dry run

Delete 12 from the tree above.

1. At 8: 12 > 8, so recurse right.
2. At 12: found it. It has two children.
3. Successor = leftmost node of the right subtree 14 → 14 itself. Copy 14 into the node.
4. Delete 14 from the right subtree: that node has no left child, so it is replaced by its right child null.
5. Result: 8 → 4, 14; 14 → left 10. In-order is 4, 8, 10, 14 — still sorted.

Java solution

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) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
        return root;
    }
}

Python solution

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            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 root.left is None:
                return root.right
            if root.right is None:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
        return root

Complexity

Edge cases and common mistakes

• Deleting the root — the function returns the new root, so always use its return value rather than assuming the old root survives.
• Forgetting to reattach — writing deleteNode(root.left, key) without assigning to root.left leaves the tree unchanged.
• Using the wrong successor — it is the minimum of the right subtree, not simply root.right.
• Key not present — the search falls off the tree and every call returns its node untouched.