Delete Node in a BST: Three Cases of Tree Surgery

You are given the root of a binary search tree and a key value. Delete the node with that key and return the updated root, keeping the BST property intact. This is LeetCode 450: Delete Node in a BST, and it is the definitive problem for understanding how BST structure changes when you remove a node.

Why this problem matters

Deleting from a BST is one of the three fundamental BST operations (search, insert, delete). Search and insert are simple recursive traversals. Deletion is where things get interesting, because removing a node with two children requires careful restructuring to keep the tree valid. If you understand this operation deeply, you understand how BSTs maintain their ordering invariant under mutation.

The key insight

There are exactly three cases when deleting a node from a BST, and each one has a clean solution:

Case 1: The node is a leaf. It has no children. Just remove it. Return None to the parent.

Case 2: The node has one child. Return that child to the parent. The child takes the deleted node's place, and the BST property is preserved because the entire subtree was already valid.

Case 3: The node has two children. This is the tricky one. You cannot just remove the node because both subtrees need a parent. The solution is to find the node's inorder successor (the smallest value in its right subtree), copy that value into the current node, and then recursively delete the successor from the right subtree. The successor has at most one child (it cannot have a left child, because then that left child would be smaller and thus the real successor), so deleting it falls into Case 1 or Case 2.

Why the inorder successor? Because it is the smallest value that is still larger than everything in the left subtree. Placing it at the deleted node's position preserves the BST ordering: everything on the left is still smaller, and everything on the right is still larger.

The solution

def deleteNode(root, key):
    if not root:
        return None

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        successor = root.right
        while successor.left:
            successor = successor.left

        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)

    return root

First, find the node. If key is less than the current value, recurse left. If it is greater, recurse right. This is the standard BST search pattern.

Then, handle the three cases. When you find the node (key == root.val), check its children. If there is no left child, return the right child (handles both the leaf case and the one-child case where only a right child exists). If there is no right child, return the left child. If both children exist, find the inorder successor by going right once and then left as far as possible.

Replace and recurse. Copy the successor's value into the current node, then delete the successor from the right subtree. The recursive call handles removing the successor cleanly, since it has at most one child.

Return the root. After modification, return root so the parent's pointer stays connected.

Visual walkthrough

Complexity analysis

Time is O(h) where h is the height of the tree. You traverse down to find the node, then potentially traverse again to find the successor. Both paths are bounded by the height. For a balanced BST, h = log n. For a skewed tree, h = n.

Space is O(h) for the recursion stack. Each recursive call adds one frame, and the maximum depth is the height of the tree.

Edge cases

• Key not in tree. The recursion reaches None and returns None. The tree is unchanged.
• Deleting the root. All three cases can apply to the root. The function returns the new root correctly.
• Single node tree. If the root is the target and has no children, return None. The tree becomes empty.
• Skewed tree (all nodes in a line). The algorithm still works, but time and space become O(n) because the height equals the number of nodes.
• Successor is the immediate right child. The while successor.left loop does not execute. The successor's value is copied, and the recursive delete removes the right child. This works correctly.

The building blocks

This problem is built on two fundamental ideas:

BST search pattern. Comparing the key against the current node's value to decide whether to go left or right. This is the same logic used in BST search and insertion. You navigate the tree by exploiting the ordering property.

Inorder successor for two-child deletion. When a node has two children, you need a replacement value that preserves the BST property. The inorder successor (smallest value in the right subtree) is the natural choice. It is guaranteed to be larger than everything in the left subtree and smaller than everything else in the right subtree.

These building blocks appear together in problems like BST insertion, BST search, and problems that require restructuring trees while maintaining sorted order.

From understanding to recall

You just traced through all three deletion cases and understand why the inorder successor works for the two-child case. The logic is clear right now. But under interview pressure, the details matter. Do you go right first and then left? Or left first and then right? Do you copy the value before or after the recursive delete? Do you delete from root.right or from root.left?

These are small details, but getting any of them wrong breaks the solution. Spaced repetition helps you lock them in. You practice writing the three cases from scratch, first after a day, then three days, then a week. After a few reps, the pattern flows naturally: search, check children, find successor, copy, recurse.

BST deletion is a pattern you will see again in problems that modify tree structure. Learning it once and reinforcing it with practice is far more efficient than re-deriving it each time.

Related posts

• Validate Binary Search Tree - Uses BST ordering properties that this deletion algorithm must preserve
• Kth Smallest Element in a BST - Another problem that relies on inorder traversal and BST structure
• Binary Search Tree Iterator - Controlled inorder traversal using the same left-spine navigation as finding the successor