Given the root of a binary search tree with distinct values and a value key, remove the node holding key (if it exists) so that the result is still a valid search tree. Use exactly these rules so the answer is unique:
- a node with no children simply disappears;
- a node with one child is replaced by that child;
- a node with two children takes over the smallest value of its right subtree, and that smallest node is deleted from the right subtree.
Return the root. If key is not in the tree, return the tree unchanged.
Examples
5 6
/ \ / \
3 8 ==> 3 8
/ \ / \ / \ \
1 4 6 9 1 4 9
Input: root = build_tree([5, 3, 8, 1, 4, 6, 9]), key = 5
Output: tree_to_list(...) == [6, 3, 8, 1, 4, None, 9]
Input: root = build_tree([5, 3, 8, 1, 4, 6, 9]), key = 3
Output: [5, 4, 8, 1, None, 6, 9]
Constraints
0 <= number of nodes <= 1000- All values are distinct
Goals
- Handle the three deletion cases: leaf, one child, two children
- Replace a node's value with its inorder successor and delete that successor instead