Construct Binary Tree from Preorder and Inorder Traversal

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

      2
     / \
    1   3

Note

You may assume that duplicates do not exist in the tree.

Solution

We can solve it recursively: in each step, use preorder to find the root node; locate the root in inorder, the left nodes are in the left subtree, the right nodes are in the right subtree.