A node with two children cannot simply be unlinked: both subtrees would come loose. The standard repair is to give the node the key of its symmetric successor — the smallest key in its right subtree — and then remove that successor, which is easy because it has no left child.
Write remove_value(root, value) returning the root after removing value, using the symmetric successor for the two-child case. A value not in the tree leaves it unchanged.
Examples
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), value = 20
Output: tree_to_list(...) == [25, 10, 30, 5, 15, None, 40]
Explanation: 25 takes the root's place and disappears from under 30.
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), value = 10
Output: tree_to_list(...) == [20, 15, 30, 5, None, 25, 40]
Constraints
0 <= number of nodes <= 10**5, keys are distinct integers- The result must be the tree this exact procedure produces, not merely some valid search tree.
Goals
- Handle all three deletion cases in one recursive function
- Replace a two-child node by its symmetric successor instead of unlinking it
- Delete the successor from the right subtree rather than splicing it by hand