Delete Node in a BST
Medium · Trees · Tree · Binary Search Tree · Binary Tree
Problem
Given the root of a binary search tree and an integer key, delete the node whose value is key (if there is one) and return the root of the resulting tree.
The result must still be a valid binary search tree holding every other value. When the deleted node has two children several trees are valid, and any of them is accepted; the tests check that the tree is a BST with exactly the right values.
Try to do it in O(height) time.
Examples
Input: root = [8,4,12,2,6,None,14], key = 12 Output: [8,4,14,2,6]
12 has only a right child, so 14 takes its place.
Input: root = [8,4,12,2,6,None,14], key = 4 Output: [8,6,12,2,None,None,14]
4 has two children; its in-order successor 6 takes its place. Putting its predecessor 2 there instead would also be accepted.
Input: root = [8,4,12], key = 5 Output: [8,4,12]
5 is not in the tree, so nothing changes.
Constraints
- The tree has between 0 and 10^4 nodes.
- -10^5 <= Node.val <= 10^5
- All values are distinct.
- root is a valid binary search tree.
- -10^5 <= key <= 10^5
Approaches
- Baseline: cut the subtree off and reinsert it — time O(s · h), space O(s)
Follow-up
Using the in-order predecessor (the rightmost node of the left subtree) is just as valid and gives a different tree, which is why any valid answer is accepted. Repeated deletions in this way can unbalance the tree; self-balancing trees (AVL, red-black) delete the same way and then rotate. The use cases below find the successor on its own, and delete a whole range of values at once.
Related problems
Start free on Cariara · Coding problems · System design studio
