Given the root of a binary search tree and a key, delete the node with that key if it exists, and return the root of the tree.
Before you code
Write the three cases down before coding. Zero children: remove. One child: splice the child in. Two children: copy in the successor's key, then delete the successor from the right subtree, which is always an easy case.
Hints
- Use the return-the-subtree-root pattern so that deleting the root needs no special case.
- The successor is the leftmost node of the right subtree.
- Answers using the predecessor instead are also accepted. The first example's expected output uses the successor (4 replaces 3).
Production & complexity notes
When solving Delete node in a BST on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Insert and delete to reinforce the underlying pattern.
What it practices
Deletion that keeps the search tree property, from Insert and delete.