363. Delete Node in a BST
You are given the root of a binary search tree and an integer key. Remove the node holding key (if it exists) and return the root of the updated tree, which must still be a valid BST.
Use the standard deletion rules, which this judge pins down exactly:
- A leaf is simply cut off.
- A node with one child is replaced by that child.
- A node with two children has its value overwritten by its in-order successor — the smallest value in its right subtree — and that successor node is then removed from the right subtree by these same rules.
If key does not appear in the tree, return it unchanged. Your function receives the root node (None for an empty tree) and the integer key, and returns the (possibly different) root.
Example 1:
Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
Output: [5, 4, 6, 2, null, null, 7]
Explanation: The node 3 has two children. Its in-order successor is 4 (the smallest value in its right subtree), so 4 takes its place and the old leaf 4 is spliced out.
Example 2:
Input: root = [5, 3, 6, 2, 4, null, 7], key = 0
Output: [5, 3, 6, 2, 4, null, 7]
Explanation: 0 is not in the tree, so nothing changes.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -10⁵ ≤ Node.val, key ≤ 10⁵
- All node values are unique.
- The input tree is a valid binary search tree.
Hints:
You never have to search both subtrees. The BST ordering steers you: if key is smaller than the current value go left, if larger go right — finding the node costs O(h).
Leaves and one-child nodes are a single pointer splice. For a two-children node, overwrite its value with the smallest value in its right subtree (walk left from the right child), then delete that node instead — it has no left child, so it falls into an easy case.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
Expected output: [5, 4, 6, 2, null, null, 7]