A warehouse keeps its part numbers (distinct integers) in a binary search tree. The stock is being
split between two sites: parts numbered below cut go to the first site and parts numbered
cut or above go to the second. Split the tree into two search trees, one per site, reusing the
existing nodes, so that inside each new tree a part sits above another part (is its ancestor)
exactly when it sat above it in the original tree. These rules decide both trees completely.
Return a list [low, high] of the two roots (None for an empty tree). cut need not be stored.
Examples
Input: root = build_tree([8, 3, 12, 1, 6, 10, 14, None, None, 4, 7]), cut = 7
Output: [tree_to_list(t) for t in ...] == [[3, 1, 6, None, None, 4], [8, 7, 12, None, None, 10, 14]]
8 3 8
/ \ / \ / \
3 12 ==> 1 6 7 12
/ \ / \ / / \
1 6 10 14 4 10 14
/ \
4 7
Input: same tree, cut = 9
Output: [[8, 3, None, 1, 6, None, None, 4, 7], [12, 10, 14]]
Constraints
0 <= number of nodes <= 2 * 10**4; the tree may be one long path- Re-inserting every part into fresh trees is far too slow on a tall tree.
Goals
- Realise that only nodes on the search path for the cut-off change their links
- Relink nodes into two trees while walking down once
- Handle very deep trees without recursion