Construct Binary Tree from Preorder and Inorder Traversal

The first element in preorder traversal is the root of the tree, which means we can find the value of root in inorder traversal. The numbers left to that value corresponds to left subtree while right part refers to right subtree. Thus, we can use dfs to continue doing this and the after popping root from preorder the left part is left subtree followed by right subtree.

Code in Python:

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            index = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[index])
            root.left = self.buildTree(preorder, inorder[0:index])
            root.right = self.buildTree(preorder, inorder[index+1:])
            return root