The symmetric successor is not the only candidate. The symmetric predecessor — the largest key in the left subtree, reached by one step left and then right as far as possible — works just as well: it is the largest key still smaller than the node's, so putting it in the node's place keeps the search order.
Write remove_predecessor(root, value), the same deletion as before but using the predecessor for the two-child case.
Examples
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), value = 20
Output: tree_to_list(...) == [15, 10, 30, 5, None, 25, 40]
Explanation: with the successor rule the root would have become 25; here 15 moves up instead.
Input: root = build_tree([2, 1, 3]), value = 2
Output: tree_to_list(...) == [1, None, 3]
Constraints
0 <= number of nodes <= 10**5, keys are distinct integers- A value not in the tree leaves it unchanged.
Goals
- Mirror the deletion rule and use the symmetric predecessor
- See that both choices are correct and give different trees
- Notice that always choosing the same side slowly skews the tree