The problem
Delete the node with a given key from a BST and return the (possibly new) root, keeping the BST property intact.
Stuck? Reveal hints one at a time
How to approach it
- 1Recurse toward the key using BST ordering; reattach the returned subtree on the way back.
- 2Found node with no children → return null. One child → return that child.
- 3Two children → find the inorder successor (leftmost node of the right subtree), copy its value into this node.
- 4Then recursively delete the successor value from the right subtree.
Key insight
The inorder successor is the smallest value larger than the deleted one — promoting it preserves "left < node < right" with the minimum disturbance.
The solution
Watch out for
- Forgetting to REASSIGN root.left/right from the recursive call loses the deletion entirely.
- The inorder predecessor (rightmost of left subtree) works symmetrically — pick one and be consistent.