pre-middle.py

def foo(first, middle):
    assert len(first) == len(middle) and set(first) == set(middle)
    if len(first) == 0:
        return None
    if len(first) == 1:
        return (first[0],)
    root = first[0]
    root_pos = middle.index(root)
    middle_left = middle[:root_pos]
    middle_right = middle[root_pos+1:]
    first_left = first[1:1+len(middle_left)]
    first_right = first[1+len(middle_left):]
    left = foo(first_left, middle_left)
    right = foo(first_right, middle_right)
    return (root, left, right)