Delete Node in a BST
Delete Node in a BST: remove the node with the given key and return the new root, keeping the binary-search-tree property intact.
- The number of nodes is in the range [0, 10⁴].
- -10⁵ <= Node.val <= 10⁵
- Each node has a unique value.
- root is a valid binary search tree.
Intuition
Search down using the BST ordering until you find the key, then split into three cases by child count. Zero or one child is a simple splice. Two children is the interesting one: overwrite the node's value with its in-order successor — the smallest value in the right subtree — then delete that successor, which by construction has at most one child.
BST deletion is the canonical three-case structural problem, and the successor trick is the reusable idea: replace a hard deletion with an easy one by moving a value rather than restructuring pointers. Returning the subtree from each recursive call — and assigning it back — is the pattern for any recursive tree modification.
Approach
Before reading on: when a node has two children, which single value could replace it so that every other node still satisfies the BST ordering? Then ask why deleting that node is easier. Aim for O(h).
Finding the node costs nothing extra
Because the tree is ordered, the search is a descent: if the key is smaller go left, if larger go right, and recurse. Assigning the recursive result back — root.left = deleteNode(root.left, key) — is what lets the parent's pointer be rewritten when a child is removed. This assignment pattern is what makes the recursive formulation so much shorter than an iterative version with an explicit parent pointer.
Zero or one child is a splice
If the node has no left child, return its right child to the caller, which links the parent straight past it. If it has no right child, return its left. A leaf falls out of the first case automatically, since its right child is null and returning null removes it. These two lines cover both the no-child and one-child situations without separate handling.
Two children: promote the in-order successor
You cannot simply drop the node — both subtrees need a parent. The successor is the leftmost node of the right subtree: the smallest value greater than the one being removed, so putting it in place preserves the ordering for every other node. Copy its value into the current node, then recursively delete the successor from the right subtree. That second deletion always lands in the easy case, because a leftmost node has no left child by definition. The mirror choice — the predecessor, largest in the left subtree — works equally well.
Solution & live demo
Common pitfalls
Not assigning the recursive result back
self.deleteNode(root.left, key)
root.left = self.deleteNode(root.left, key)
The recursion returns the new subtree root, which may differ after a deletion. Discarding it leaves the parent pointing at the removed node, so the tree is unchanged or corrupted.
Taking the successor from the wrong side
successor = root.left while successor.left: ...
successor = root.right while successor.left: ...
The in-order successor is the smallest value in the right subtree, reached by going right once then left as far as possible. Descending left from the start finds an unrelated node and breaks the ordering.
Forgetting to delete the duplicated successor
root.val = successor.val return root
root.val = successor.val root.right = self.deleteNode(root.right, successor.val)
Copying the value leaves two nodes holding it. The original successor must be removed from the right subtree, and that deletion is guaranteed to hit the easy case since a leftmost node has no left child.
Edge cases
The descent reaches null and returns it, leaving the tree unchanged.
Both children are null, so returning the right child returns null and the leaf is removed.
The function returns the new root, so the caller's reference is updated correctly.
The no-right-child branch returns the left subtree, splicing it into the parent.
The initial null check returns null immediately.