Rebuild a Tree from Traversals

There are two common ways to list the values of a binary tree. Preorder lists the node, then its left subtree in preorder, then its right subtree in preorder. Inorder lists the left subtree in inorder, then the node, then the right subtree in inorder. When every value is different, the two lists together pin down exactly one tree.

Write rebuild(preorder, inorder) that builds that tree with the provided Node class and returns its root (None when the lists are empty). The tests read your tree with the provided to_list, which lists it in level order with None for a missing child.

Examples

      10
     /  \
    6    14
   / \     \
  2   8     20
           /
          17

to_list(rebuild([10, 6, 2, 8, 14, 20, 17], [2, 6, 8, 10, 14, 17, 20]))
# returns [10, 6, 14, 2, 8, None, 20, None, None, None, None, 17]

to_list(rebuild([1, 2], [2, 1]))  # returns [1, 2]
to_list(rebuild([1, 2], [1, 2]))  # returns [1, None, 2]

The drawing shows the first tree. In the second and third examples the preorder lists are the same, and the inorder list is what tells you whether 2 hangs to the left or to the right of 1.

Constraints

• 0 to 2,000 values, all different integers.
• Both lists hold the same values and come from a real tree.