The key observation is that in the pre-order traversal, the root always come first in the list. Thus , one can use a recursion to build the tree by fetching the corresponding inorder/preorder traversal segments to further construct the tree. The running time is O(N) if one preprocess the data to create a hash table to map the keys in the in-order List with its index.