#450
Delete Node in a BST
Medium Three deletion cases
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Delete the node with a given key from a BST and return the new root.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: remove a value and keep it a BST.
Why this works: a leaf or one-child node is replaced by its child. A two-child node takes the smallest value from its right subtree, which is then deleted there.
Example: delete 3 from 5 (3 (2, 4), 6)
3 has two children → successor 4copy 4 into the node, delete the old 4 → 5 (4 (2), 6)
✦Hints open one at a time
Leaf or one child: replace the node with its child (or null).
Two children: copy in the smallest value of the right subtree (the inorder successor), then delete that value from the right subtree.
↗Approach
Recurse to find the key. Handle the three cases. The successor is found by going right once and then left as far as possible.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (root.left == null) return root.right; // 0 or 1 child
if (root.right == null) return root.left;
TreeNode succ = root.right;
while (succ.left != null) succ = succ.left; // smallest on the right
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}
}!Common mistake
Copying the successor's value but forgetting to delete the successor node, leaving a duplicate.
Complexity
- Time: O(h).
- Space: O(h).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon