Removing a node from a search tree is easy as long as it has at most one child: it is simply replaced by that child, or by nothing when it has none. The search order survives, because everything in that child's subtree was already on the same side of the parent.
Write remove_simple(root, value) returning the root of the tree with value removed. The node holding value is guaranteed to have at most one child, and a value that is not in the tree leaves it unchanged.
Examples
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), value = 5
Output: tree_to_list(...) == [20, 10, 30, None, 15, 25, 40]
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), value = 15
Output: tree_to_list(...) == [20, 10, 30, 5, None, 25, 40]
Constraints
0 <= number of nodes <= 10**5, keys are distinct integers- The node removed has no children or exactly one.
Goals
- Splice a node out by promoting its only child
- Treat a leaf as the case where that child is nothing
- Keep the parent's link correct by returning the new subtree