Build an AVL tree by inserting keys in order, then remove each key of removals in order, ignoring any that is not present. Return the final tree as a level-order list.
Removal follows the usual three cases: a leaf simply goes; a node with one child is replaced by that child; a node with two children takes the value of its symmetric successor, the smallest key in its right subtree, which is then removed from there. Afterwards every node on the path back to the root has its height refreshed and is rebalanced if its factor has reached 2 or -2.
Examples
Input: keys = [20, 10, 30], removals = [10]
Output: tree_to_list(...) == [20, None, 30]
Input: keys = [20, 10, 30, 25], removals = [10]
Output: tree_to_list(...) == [25, 20, 30]
Explanation: removing 10 leaves 20 right-heavy with a left-heavy right child, so the RL case lifts 25.
Constraints
0 <= len(keys) <= 10**4,0 <= len(removals) <= 10**4, values are integers- Unlike insertion, a deletion can unbalance several ancestors, so do not stop at the first rotation.
Goals
- Remove a node from a search tree by its symmetric successor
- Rebalance every ancestor on the way back up, not just the first
- Handle the balance-0 child, the case insertion never produces