Delete Node in a BST
Understanding the Problem
We need to delete a node with a specific value from a Binary Search Tree while keeping the BST property intact. The BST property says that for every node, all values in its left subtree are smaller and all values in its right subtree are larger.
Finding the node is the easy part: compare the key with the current node and go left or right. Removing the node once found is harder. A node with no children can be removed directly. A node with one child is replaced by that child. A node with two children cannot be removed outright because both subtrees would lose their parent; we need a replacement value that keeps the BST ordering valid.
The in-order successor (the smallest value in the right subtree) or the in-order predecessor (the largest value in the left subtree) can always serve as that replacement. Either one sits at the boundary between the two subtrees, so promoting it preserves the BST property.
Key Constraints:
Number of nodes in [0, 10^4]→ The tree can be empty, so we need to handle null root. With up to 10,000 nodes, any O(n) approach is fine.-10^5 <= Node.val <= 10^5→ Standard integer range, no overflow concerns.Each node has a unique value→ No duplicates. The key either exists exactly once or not at all.root is a valid BST→ We can rely on the BST property for searching. We don't need to validate the tree.
Approach 1: Recursive BST Deletion
Intuition
The BST property lets us navigate directly to the target: if the key is less than the current node's value, the target is in the left subtree; if greater, it is in the right subtree. The search takes O(h) time, where h is the height of the tree.
Once we find the node, deletion breaks down into three cases based on how many children it has:
- Leaf node (no children): Remove it by returning null to the parent.
- One child: Return the only child so it takes over the deleted node's position.
- Two children: Both subtrees need a parent, so the node cannot be dropped. Instead, find the in-order successor (the smallest value in the right subtree), copy its value into the current node, then delete the successor from the right subtree.
Each recursive call returns the root of its (possibly updated) subtree, and the caller reassigns root.left or root.right to whatever comes back. This return-value contract is how the tree gets stitched back together without tracking any parent pointers.
Two facts make the two-children case safe. First, the successor is the smallest value greater than the deleted key, so it is larger than everything in the left subtree and smaller than everything else in the right subtree; copying it into the deleted node's slot preserves the BST ordering. Second, the successor is the leftmost node in the right subtree, so it has no left child, and deleting it always falls into the leaf or one-child case. The recursion cannot loop forever on case 3.
Algorithm
- If the root is null, return null (key not found or empty tree).
- If the key is less than
root.val, recurse on the left subtree and updateroot.left. - If the key is greater than
root.val, recurse on the right subtree and updateroot.right. - If the key equals
root.val, we found the node to delete: - If it has no left child, return its right child.
- If it has no right child, return its left child.
- If it has both children, find the in-order successor (smallest node in right subtree), copy its value to the current node, then recursively delete the successor from the right subtree.
- Return the root.
Visualization and Code
Loading animation...
- Time Complexity: O(h), where h is the height of the tree. Searching for the node takes O(h), finding the in-order successor takes O(h), and deleting the successor is another O(h). For a balanced BST, h = O(log n). For a skewed tree, h = O(n).
- Space Complexity: O(h). The recursion stack goes as deep as the height of the tree. For a balanced BST, this is O(log n). For a skewed tree, O(n).
The recursion stack is the only non-constant cost in this solution. The next approach removes it by tracking the parent explicitly and rewiring pointers in a loop.
Approach 2: Iterative BST Deletion
Intuition
The iterative version handles the same three cases but replaces the call stack with explicit pointer tracking. While searching, we keep a reference to the parent of the current node, because deleting a node means updating the parent's left or right pointer.
For the two-children case, we find the in-order successor and its parent, copy the successor's value into the target node, then redirect the deletion to the successor. After that reduction, the node being deleted has at most one child, so the final step is a single pointer update: the parent replaces the node with its only child (or null). The result is the same O(h) running time with O(1) extra space.
Algorithm
- Search for the node iteratively, keeping track of both the current node and its parent.
- If the node isn't found, return the root unchanged.
- If the node has two children:
- Find the in-order successor (leftmost node in the right subtree) and its parent.
- Copy the successor's value into the node to delete.
- Now the problem reduces to deleting the successor, which has at most one child.
- The node to delete now has at most one child. Determine the child (left, right, or null).
- If the node is the root, return the child as the new root.
- Otherwise, update the parent's left or right pointer to point to the child.
Visualization and Code
Loading animation...
- Time Complexity: O(h), where h is the height of the tree. Same as the recursive approach. We traverse at most the height to find the node, then at most the height again to find and delete the successor. For a balanced BST, O(log n). For a skewed tree, O(n).
- Space Complexity: O(1). No recursion, no extra data structures. We only use a constant number of pointer variables.