Remove a Key From a Search Tree
Implement removeKey
You are given the root of a binary search tree with distinct values and a key. Remove the node holding the key (if there is one) so that the tree remains a valid binary search tree, and return the root of the result. Use this rule for the shape: a leaf is deleted; a node with one child is replaced by that child; a node with two children takes over the value of its inorder successor (the smallest value in its right subtree) and the successor node is deleted instead.
The removal can be written recursively, or iteratively by remembering the parent of the node being unlinked.
Example 1:
Input: root = [50,30,70,20,40,60,80,null,null,35,45,null,65], key = 30
Output: [50,35,70,20,40,60,80,null,null,null,45,null,65]
Example 2:
Input: root = [50,30,70,20,40,60,80,null,null,35,45,null,65], key = 60
Output: [50,30,70,20,40,65,80,null,null,35,45]
Example 3:
Input: root = [50,30,70,20,40,60,80,null,null,35,45,null,65], key = 90
Output: [50,30,70,20,40,60,80,null,null,35,45,null,65]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ●
key is any value between 0 and 1000; if it is not in the tree, nothing changes - ●
Remove the node holding key so the tree stays a valid binary search tree, using this rule: a leaf is simply removed; a node with one child is replaced by that child; a node with two children takes over the value of its inorder successor (the smallest value in its right subtree), and that successor node is then removed instead. Return the root of the resulting tree (checked as a level-order list)
root =
key =