Delete a Node from a BST

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7. All trees in this topic that are called BSTs have different values.

Delete the node with the value key (if it exists) and return the root of the BST. When the node has two children, replace it by its inorder successor (the smallest value of its right subtree), so that the answer is unique.

For [5, 3, 6, 2, 4, None, 7] and key = 3 the answer is [5, 4, 6, 2, None, None, 7].

Examples

Example 1

Input:

delete_node(root, 3)  # root = [5, 3, 6, 2, 4, None, 7]

Output:

[5, 4, 6, 2, None, None, 7]

Example 2

Input:

delete_node(root, 0)  # root = [5, 3, 6, 2, 4, None, 7]

Output:

[5, 3, 6, 2, 4, None, 7]

Constraints

• 0 <= number of nodes <= 100000
• The tree is a BST, not deeper than 800 levels.