Delete a Node in a Binary Search Tree
Remove the node with a given value from a binary search tree while preserving its ordering property.
Given the root of a binary search tree (BST) and an integer key, delete the node with value key from the tree if it exists, and return the root of the resulting BST.
If no node has value key, return the tree unchanged.
Deleting a node generally requires one of three cases:
- The node has no children. Simply remove it.
- The node has exactly one child. Replace the node with that single child.
- The node has two children. There are multiple ways to preserve the BST property here, so to make the answer unique, use this exact rule: replace the node's value with its in-order successor (the smallest value in its right subtree), then delete that successor's original node from the right subtree (the successor itself is guaranteed to have at most one child, so removing it falls back into case 1 or 2).
Example 1
Input: root = [5,3,8,2,4,7,9], key = 5
Output: [7,3,8,2,4,null,9]
Explanation: 5 has two children. Its in-order successor is the smallest value in its right subtree (7), so 5 is replaced by 7, and the original leaf node 7 is removed from the right subtree.
Example 2
Input: root = [5,3,8,2], key = 3
Output: [5,2,8]
Explanation: 3 has exactly one child (2), so 3 is replaced by that child.
Example 3
Input: root = [5,3,8,2,4,7,9], key = 100
Output: [5,3,8,2,4,7,9]
Explanation: No node has value 100, so the tree is returned unchanged.
Constraints
- The number of nodes in the tree is in the range [0, 10000].
- -100000 <= Node.val <= 100000
- root is guaranteed to be a valid binary search tree.
- All node values are unique.
- -100000 <= key <= 100000
Follow-up
What would change if you used the in-order predecessor (the largest value in the left subtree) instead of the successor for the two-children case?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.