Insert keys into an initially empty AVL tree, one at a time, in the order given. After every insertion, walk back up to the root and rebalance the first node whose balance factor has reached 2 or -2, using the single or double rotation its case calls for. Keys already present are ignored.
Return the finished tree as a level-order list.
Examples
Input: keys = [10, 20, 30]
Output: tree_to_list(...) == [20, 10, 30]
Explanation: after 30 arrives, node 10 is right-heavy with a right-heavy child, so one left rotation lifts 20.
Input: keys = [30, 20, 10]
Output: tree_to_list(...) == [20, 10, 30]
Constraints
0 <= len(keys) <= 10**4, values are integers- Heights count an empty tree as 0.
Goals
- Insert into a search tree and restore the AVL condition on the way back up
- Apply the right single or double rotation at the lowest unbalanced node
- Keep sorted input from degenerating into a chain