Delete Node in a BST
Problem Statement
Given the root of a BST and an integer key, delete the node with value key if it exists and return the root of the updated BST. If key is not present, return the original tree.
Input
A BST root and an integer key to remove if present.
Output
The root of a BST containing every original value except key, if key existed.
Constraints
- •
0 <= number of nodes <= 10^4 - •
-10^5 <= Node.val <= 10^5 - •
All node values are unique - •
-10^5 <= key <= 10^5
Examples
Example 1
root = **[5,3,6,2,4,null,7]**, key = **3**
**[5,4,6,2,null,null,7]**Example 2
root = **[5,3,6,2,4,null,7]**, key = **0**
**[5,3,6,2,4,null,7]**Example 3
root = **[]**, key = **5**
**[]**Learning Objectives
- Break BST deletion into leaf, one-child, and two-child cases.
- Use the inorder successor to preserve ordering when deleting a node with two children.
- Reconnect subtree roots correctly through recursive returns.
- Explain why deleting the successor after copying its value avoids duplicate values.
Intuition
Pattern Recognition
The signal is removing a value from a BST while preserving sorted order. First use normal BST search to find the node. The hard part begins once the node is found: deletion must return a valid replacement subtree to the parent.
There are three cases. A leaf can become null. A node with one child can be replaced by that child. A node with two children needs a value that fits between the entire left and right subtrees. The inorder successor, the smallest node in the right subtree, is the standard choice because it is greater than everything on the left and no greater than the remaining right subtree values. This is the hardest BST operation because search, structural replacement, and recursive reconnection all happen together.
Common mistakes
- ×Deleting a two-child node by returning only one child and losing the other subtree.
- ×Copying the successor value but forgetting to delete the original successor node, creating a duplicate.
- ×Using the immediate right child as the successor without walking to the leftmost node of the right subtree.
- ×Not assigning **root.left** or **root.right** to the returned subtree after recursive deletion.
Algorithm Explanation
Key idea
Search for key using BST ordering. When the node is found, return the subtree that should replace it. No child means null. One child means that child. Two children means replace the node value with the inorder successor, then delete that successor from the right subtree so every value appears exactly once.
Recursion walkthrough
Use [5,3,8,2,4,7,9] and delete 5. The target is the root and has two children. The right subtree is rooted at 8. Walk left inside that right subtree to find the smallest value, 7. Replace the root value 5 with 7. Now the tree temporarily has two 7 values, so recursively delete 7 from the right subtree. That recursive call goes from 8 to its left child 7. Since that 7 is a leaf, it returns null, and 8.left becomes null. The final tree keeps all values except 5 and remains a BST.
For a one-child case, if deleting a node whose only child is 4, the recursive call simply returns 4 to the parent. For a leaf, it returns null. These returned roots are what reconnect the tree correctly.
Algorithm
- If root is null, return null.
- If key < root.val, delete from root.left and assign the returned subtree to root.left.
- If key > root.val, delete from root.right and assign the returned subtree to root.right.
- Otherwise the target node is found. If it has no left child, return root.right.
- If it has no right child, return root.left.
- If it has two children, find the smallest node in root.right.
- Copy that successor value into root.val.
- Delete the successor value from root.right and assign the returned subtree to root.right.
- Return root.
Correctness reasoning
Search only descends into the subtree that can contain key, so values outside that path remain unchanged. In the leaf and one-child cases, the returned replacement subtree already satisfies all ancestor bounds. In the two-child case, the inorder successor is the smallest value greater than the deleted node, so it is greater than every value in the left subtree and no larger than any remaining value in the right subtree. Removing the original successor prevents duplication. Therefore each case returns a valid BST containing exactly the original values minus key.
Solutions
Solution: Recursive deletion with inorder successor
Use this canonical solution in interviews. It is concise, handles all three structural cases, and makes the successor reasoning explicit.
Recursively search for the key. Once found, return the correct replacement subtree. For two children, copy the inorder successor value and then delete that successor from the right subtree.
Step-by-step
- Return null for an empty subtree.
- Recurse left or right according to the comparison with key, assigning the returned subtree back to that child pointer.
- When root.val equals key, handle the zero-child and one-child cases by returning the non-null child, or null if none exists.
- For two children, find the leftmost node in the right subtree.
- Copy the successor value into root.val.
- Delete the successor value from root.right so it appears only once.
- Return root after its children have been repaired.
O(h)
O(h)
Search and successor removal follow downward paths. The recursion stack is O(log n) balanced and O(n) skewed.
Java implementation
Dry Run
Sample input
root = [5,3,8,2,4,7,9], key = 5. Deleting the root demonstrates the two-child successor case.
| step | current node | comparison or case | tree action | subtree returned |
|---|---|---|---|---|
| 1 | 5 | key equals current node | node has two children | must replace with successor |
| 2 | right subtree rooted at 8 | find minimum | walk left to 7 | successor is 7 |
| 3 | 5 | copy successor | root value becomes 7 | right subtree still contains old 7 |
| 4 | 8 | delete successor 7 from right subtree | go left | 8 after its left child is updated |
| 5 | 7 | leaf target | return null | 8.left becomes null |
The final root value is 7, the old successor leaf is removed, and all values still satisfy the BST ordering.
Interview Tips
Walk the three cases slowly. Interviewers often care less about typing speed and more about whether you can explain why the successor is safe. After copying the successor value, explicitly delete that successor from the right subtree; otherwise you leave duplicate values and the tree is no longer the requested result.
Likely follow-ups
- Could you use the inorder predecessor from the left subtree instead of the successor?
- How would deletion work in an iterative implementation with parent pointers?
- How would a self-balancing BST restore balance after deletion?
- What extra updates are needed if each node stores subtree size or height?
Similar Problems
Key Takeaways
- BST deletion has three structural cases: leaf, one child, and two children.
- A one-child node can be replaced directly by its child.
- A two-child node is safely replaced by its inorder successor, the smallest node in the right subtree.
- After copying the successor value, delete the original successor node to avoid duplicates.