Delete Node in a BST — Solution

Problem

Given the root of a binary search tree and a key value, remove the node with that key and return the root of the updated tree. If the key is not present, return the tree unchanged. All BST properties must hold after deletion.

[5,3,6,2,4,null,7]

• Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
• Output: [5, 4, 6, 2, null, null, 7]
• Explanation: Node 3 is replaced by its in-order successor 4, which is then removed from its original position.

Intuition

Deletion from a BST has three cases depending on how many children the target node has. The tricky case is when both children are present — you can't simply splice the node out. The key insight is that the in-order successor (the smallest value in the right subtree) can slot into the deleted node's position and preserve BST ordering, so you copy its value down and then delete the simpler successor node recursively.

Solution — Recursive BST Deletion

Navigate the tree using BST ordering to find the target, then handle the three deletion cases: no children, one child, or two children.

1. If root is null, the key isn't in the tree — return null.
2. If key < root.val, recurse into the left subtree and update root.left.
3. If key > root.val, recurse into the right subtree and update root.right.
4. If key == root.val (found the node):
   • If no left child, return root.right (right subtree replaces it).
   • If no right child, return root.left.
   • Both children present: find the in-order successor (walk right once, then all the way left). Copy its value into the current node, then delete the successor from the right subtree.
5. Return root.

1def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
2    if not root:
3        return None  # key not found, or empty tree — nothing to delete
4
5    if key < root.val:
6        root.left = self.deleteNode(root.left, key)
7    elif key > root.val:
8        root.right = self.deleteNode(root.right, key)
9    else:
10        if not root.left:
11            return root.right  # no left child — right subtree takes this node's place
12        if not root.right:
13            return root.left   # no right child — left subtree takes this node's place
14
15        # find in-order successor: smallest node in the right subtree
16        successor = root.right
17        while successor.left:
18            successor = successor.left
19
20        root.val = successor.val  # overwrite current node's value with successor's
21        root.right = self.deleteNode(root.right, successor.val)  # remove successor from right subtree
22
23    return root

Time: O(h) where h is the tree height — O(log n) average for a balanced BST, O(n) worst case for a skewed tree. Space: O(h) — the recursion stack depth equals the height of the tree.

Complexity Summary

Common Mistakes

• Missing the base case for a key not in the tree — if the key doesn't exist, the recursion walks off the tree to a null node. Without if not root: return None, this crashes. The correct behavior is to return null and let the parent pointer remain unchanged.
• Not deleting the successor after copying its value — after writing root.val = successor.val, you must call deleteNode(root.right, successor.val) to actually remove the successor from the right subtree. Skipping this leaves a duplicate in the tree.
• Going left instead of right to find the successor — the in-order successor is the minimum of the right subtree: go right once, then left as far as possible. Going left from the current node finds the in-order predecessor, which also works but requires different code.
• Trying to relink nodes instead of copying values — when both children are present, it's tempting to splice the successor node directly into the tree. This is error-prone because you must also reroute the successor's right child. Copying the value down and deleting the simpler successor is both cleaner and correct.
• Assuming a balanced tree — interview follow-ups often ask about time complexity. The answer is O(log n) only for balanced BSTs. A degenerate (skewed) BST degrades to O(n), the same as a linked list.

Related Problems

• search-in-a-binary-search-tree — the same BST navigation pattern (go left if smaller, right if larger) without the deletion complexity
• kth-smallest-element-in-a-bst — relies on in-order traversal of a BST, the same ordering property used to find the successor here
• lowest-common-ancestor-of-a-binary-search-tree — BST key comparisons to navigate toward a target, same structural approach
• recover-binary-search-tree — restoring broken BST structure by identifying and swapping misplaced nodes
• convert-sorted-array-to-binary-search-tree — constructing BSTs, builds intuition for why BST height depends on insertion order