512. Remove a Key
A library keeps catalogue numbers in a binary search tree: smaller numbers lie in the left subtree and larger numbers in the right subtree. The book with catalogue number key has been withdrawn, so its entry must disappear.
Delete the node holding key from the tree root and return the root of the resulting tree. The result must still be a valid search tree containing every remaining key exactly once. If key does not occur, the tree stays as it is, and an empty tree stays empty. Several shapes can be correct, for instance a node with two children may be replaced by its in-order successor or by its predecessor, and any valid result is accepted.
Example 1
- Input:
- root = [7,3,10,1,5,8,12], key = 3
- Output:
- [7,5,10,1,null,8,12]
- Explanation:
Key 3 has two children; replacing it by its in-order successor 5 gives [7,5,10,1,null,8,12], and any other valid search tree holding keys 1, 5, 7, 8, 10, 12 is accepted too.
Example 2
- Input:
- root = [7,3,10,1,5,8,12], key = 6
- Output:
- [7,3,10,1,5,8,12]
- Explanation:
Key 6 is not in the tree, so the tree is returned unchanged.
Constraints
0 ≤ number of nodes ≤ 104
-1000 ≤ node key, key ≤ 1000
All keys in the tree are distinct and root is a valid binary search tree.
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(h)
- Space
- O(h)