Solving tips
- Split into two phases: use the BST property to descend to the node in O(h), then handle deletion by case.
- Three cases: leaf returns None, one child returns that child, two children replace the value with the in-order successor (min of right subtree) then recursively delete that successor.
- Always reattach the recursive result: root.left = self.deleteNode(root.left, key) — forgetting the assignment loses the spliced subtree, and returning root at the end handles deleting the actual root.
- Pitfall: after copying succ.val into the node, recurse on the right subtree with succ.val (not the original key), and don't assume the successor is a leaf — it may have a right child. O(h) time and space.
Problem
You are given the root of a Binary Search Tree (BST) and a value key. Delete the node whose value equals key, if it exists, and return the root of the resulting tree. The tree must remain a valid BST after the deletion.
Recall the BST property: every left descendant is smaller than a node and every right descendant is larger. Deleting a node with two children requires replacing it with a value that preserves this ordering.
If key is not in the tree, return the tree unchanged.
Examples
Example 1
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Node 3 has two children (2 and 4). Replace 3 with its in-order successor 4 (the smallest value larger than 3), then remove that successor from its old spot.
Example 2
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
There is no node with value 0, so the tree is returned unchanged.
Example 3
Input: root = [5,3,6,2,4,null,7], key = 6
Output: [5,3,7,2,4]
Node 6 has only a right child 7, so 6 is simply replaced by 7.
Constraints
- The number of nodes is in the range
[0, 10^4].
-10^5 <= Node.val <= 10^5- Each node has a unique value.
-10^5 <= key <= 10^5
Think about it first
Hint 1
Use the BST property to *find* the node in O(h): go left if key < node.val, right if key > node.val. The interesting part is what to do once you find it.
Hint 2
Three cases for the found node: no children (just remove it), one child (splice the child in), two children (the tricky case). Handle them separately.
Hint 3
For a node with two children, replace its value with its in-order successor — the smallest value in its right subtree — then recursively delete that successor from the right subtree. (The in-order predecessor, the largest value in the left subtree, works symmetrically.)
TL;DR
Recursively locate the node, then handle 0/1/2-child cases — replacing a two-child node with its in-order successor — O(h) time, O(h) space.
Approach 1 — Recursive delete with successor replacement
There is no meaningful “brute force” here: rebuilding the tree from a filtered value list would destroy its shape and cost O(n log n). The canonical solution walks straight to the node using the BST property and handles three cases.
The insight: deletion splits into three shapes. A leaf (no children) is removed by returning None. A node with one child is removed by returning that child (it slots into the parent’s link). A node with two children cannot just be dropped — replace its value with its in-order successor (the smallest value in the right subtree, which is larger than everything on the left and smaller than everything else on the right), then delete that successor, which by construction has at most one child.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional
class Solution:
def deleteNode(
self, root: Optional[TreeNode], key: int
) -> Optional[TreeNode]:
if not root:
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:
# Found the node to delete.
if not root.left:
return root.right # 0 or 1 (right) child
if not root.right:
return root.left # 1 (left) child
# Two children: find in-order successor (min of right subtree).
succ = root.right
while succ.left:
succ = succ.left
root.val = succ.val
root.right = self.deleteNode(root.right, succ.val)
return root
Walkthrough on Example 1 (root = [5,3,6,2,4,null,7], key = 3):
- At
5: 3 < 5 → recurse left, will reassign 5.left.
- At
3: match. It has two children (2 and 4).
- Find successor = min of right subtree rooted at
4 → 4 (it has no left child).
- Overwrite:
3.val = 4. Node is now 4.
- Delete
4 from the right subtree: deleteNode(node(4), 4) matches at 4, which is a leaf → returns None, so the node’s right child becomes None.
- The subtree is now
4 with left child 2, right child None. Back up, 5.left = this subtree.
- Result
[5,4,6,2,null,null,7]. ✓
Complexity: O(h) time — one downward path to find the node, plus at most one more path to find/delete the successor. O(h) space for the recursion stack (h = height; O(n) worst case, O(log n) balanced).
Approach 2 — In-order predecessor variant
The insight: the two-child case is symmetric — you may equally replace the node with its in-order predecessor, the largest value in the left subtree, then delete that predecessor from the left. Both keep the BST valid; the choice is stylistic (or used to balance which side shrinks).
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from typing import Optional
class Solution:
def deleteNode(
self, root: Optional[TreeNode], key: int
) -> Optional[TreeNode]:
if not root:
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 not root.left:
return root.right
if not root.right:
return root.left
# Two children: use in-order predecessor (max of left subtree).
pred = root.left
while pred.right:
pred = pred.right
root.val = pred.val
root.left = self.deleteNode(root.left, pred.val)
return root
Walkthrough on Example 3 (key = 6): descend 5 → 6 (6 > 5). At 6: root.left is None, so return root.right = node 7. The parent link 5.right becomes 7. Result [5,3,7,2,4]. ✓ — the one-child case never touches the predecessor logic.
Complexity: O(h) time, O(h) space — identical to Approach 1.
Common pitfalls
- Reattaching the recursive result: you must write
root.left = self.deleteNode(root.left, key) (and likewise for the right). Calling deleteNode without assigning its return value loses the spliced subtree.
- Deleting the successor’s value, not re-deleting the whole key: after copying
succ.val into root, recurse on the right subtree with succ.val — recursing with the original key would loop or fail since root.val changed.
- Successor with a right child: the in-order successor is the leftmost node of the right subtree; it has no left child but may have a right child. The recursive delete handles that via the one-child case, so do not assume it is a leaf.
- Empty tree / key absent: returning
None at the base case and simply not matching means an absent key leaves the tree unchanged (Example 2).
- Updating the parent link when the root itself is deleted: because every branch returns a node (or
None) that the caller reassigns, deleting the actual root correctly returns the new root — do not forget to return root at the end.
Pattern takeaway
BST mutation problems follow a “recurse to locate, then fix up on the way back” shape: use the ordering to descend in O(h), and let each call return the (possibly new) subtree root so the parent relinks it. For two-child deletion, swap in the in-order successor or predecessor — the unique neighbouring value that preserves the sorted invariant — reducing the hard case to an easy one.