877. Delete Node in Binary Search Tree

Given the root of a binary search tree and a key, delete the node with that key (if present) while keeping the BST valid, and return the resulting tree as a level-order array. When the deleted node has two children, replace it with its in-order successor (the smallest value in its right subtree). The input gives a level-order BST array and the key separated by ' | '.

Input: A level-order BST array and the key, separated by ' | '.

Output: Array — the resulting BST in level order.

Examples

Input: [5,3,6,2,4,null,7] | 3
Output: [5,4,6,2,null,null,7]
Explanation: 3 is replaced by its successor 4.

Input: [5,3,6,2,4,null,7] | 0
Output: [5,3,6,2,4,null,7]
Explanation: Key absent; tree unchanged.

Input: [5] | 5
Output: []
Explanation: Deleting the only node empties the tree.

Constraints

• 0<=nodes<=10^4
• valid BST
• -10^5<=key<=10^5

Asked by