Description
Given a root node of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated).
Examples
Input:
root = [5,3,6,2,4,null,7], key = 3Output:
[5,4,6,2,null,null,7]Explanation:
Delete node 3, replace with inorder successor.
Input:
root = [8,4,12,2,6,10,14], key = 12Output:
[8,4,14,2,6,10,null]Explanation:
Delete node 12 which has two children. Replace it with its inorder successor 14. Node 14 moves up and its original position becomes null since it had no children.
Input:
root = [15,10,20,8,12,18,25], key = 15Output:
[18,10,20,8,12,null,25]Explanation:
Delete the root node 15 which has two children. Replace it with its inorder successor 18. The tree structure is maintained with 18 as the new root, and 18's original position becomes null.
Constraints
- •
0 ≤ number of nodes ≤ 10⁴ - •
-10⁵ ≤ Node.val ≤ 10⁵