Delete Node in a BST
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Follow up: Could you solve it with time complexity O(height of tree)?
Example 1
5 5
/ \ -> / \
3 6 4 6
/ \ \ / \
2 4 7 2 7Input
root = [5,3,6,2,4,null,7], key = 3Output
[5,4,6,2,null,null,7]Given key to delete is 3, so we find the node with value 3 and delete it; one valid resulting BST is shown.
Example 2
5 5
/ \ / \
3 6 -> 3 6
/ \ \ / \ \
2 4 7 2 4 7Input
root = [5,3,6,2,4,null,7], key = 0Output
[5,3,6,2,4,null,7]The tree does not contain a node with value 0, so it remains unchanged.
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.
rootis a valid binary search tree.-10^5 <= key <= 10^5