Delete a node with a given key from a binary search tree while preserving the BST property.
Problem
You are given the root of a binary search tree (BST) and an integer key.
Remove the node whose value equals key from the tree, and return the root of the modified BST.
After deletion, the tree must still satisfy the BST ordering property:
- values in the left subtree are smaller than the node value
- values in the right subtree are larger than the node value
If the key does not exist in the tree, return the tree unchanged.
When the node to delete has two children, replace it with a valid BST successor or predecessor strategy so the tree remains valid.
Input Format
root: the root node of a BSTkey: integer value to delete
Output Format
Return the root node of the BST after removing key.
Constraints
- The tree is a valid BST before deletion.
- Node values are typically distinct.
- If
keyis not present, the tree should remain unchanged. - Preserve BST ordering after deletion.
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 it with its inorder successor 4, then delete the original 4 node.
Example 2
Input
root = [5,3,6,2,4,null,7], key = 0
Output
[5,3,6,2,4,null,7]
Explanation
The key is not present, so the BST stays the same.
Show 1 more example
Example 3
Input
root = [], key = 1
Output
[]
Explanation
An empty tree remains empty after deletion.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.