Delete Node in a BST

I asked this in my own interview loops because the third case (the node has two children) is one of the cleanest tests of whether a candidate genuinely groks BST ordering. People who only memorize the rule "replace with in-order successor" without understanding why fall apart on the recursive cleanup step. The catalog covers Insert into BST and Validate BST but skipped this one, which is the harder half of the pair.

Delete Node in a BST

Given the root of a binary search tree and a key value key, delete the node with the given key in the BST. Return the root of the BST (which can be modified). It is acceptable for any valid BST that no longer contains key to be returned.

Basically, the deletion can be divided into three steps:

1. Search for the node to remove.
2. If the node is found, delete the node.
3. The resulting tree must still be a valid BST.

Examples

Example 1:

• Input: root = [5, 3, 6, 2, 4, null, 7], key = 3
• Output: [5, 4, 6, 2, null, null, 7]
• Explanation: Node 3 has two children. Replace its value with the in-order successor (4), then delete the successor from the right subtree of 3.

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 the tree is returned unchanged.

Example 3:

• Input: root = [], key = 0
• Output: []
• Explanation: Empty tree stays empty.

Example 4:

• Input: root = [5, 3, 6, 2, 4, null, 7], key = 7
• Output: [5, 3, 6, 2, 4]
• Explanation: 7 is a leaf, so we just snip it.

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5.
• Each node has a unique value.
• root is a valid BST.
• -10^5 <= key <= 10^5.

Follow-up

Can you do it in O(h) time where h is the height of the tree? The straightforward recursion already does, but make sure your two-children case does not accidentally walk the same subtree twice.