# 105. Construct Binary Tree from Preorder and Inorder Traversal

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

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

Example:

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

# Solution

Approach 1: recursion.

# Code (Python)

Approach 1:

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # time: each search takes N, at best logN times, at worse N times, so worse case O(N^2)
        return self._build(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
    
    def _build(self, preorder, start1, end1, inorder, start2, end2):
        if start1 > end1:
            return None
        if start1 == end1:
            return TreeNode(preorder[start1])
        root = TreeNode(preorder[start1])
        len_left = inorder.index(root.val, start2) - start2
        root.left = self._build(preorder, start1 + 1, start1 + len_left, inorder, start2, start2 + len_left)
        root.right = self._build(preorder, start1 + len_left + 1, end1, inorder, start2 + len_left + 1, end2)
        return root

# Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* doBuildTree(vector<int>& preorder, int pHead, int pTail, vector<int>& inorder, int iHead, int iTail) {
        if (pHead > pTail || iHead > iTail)
            return NULL;
        int i;
        for (i = iHead; i <= iTail; ++i)
        {
            if (inorder[i] == preorder[pHead])
                break;
        }
        int iLeftHead = iHead;
        int iLeftTail = i - 1;
        int iRightHead = i + 1;
        int iRightTail = iTail;
        int pLeftHead = pHead + 1;
        int pLeftTail = pLeftHead + iLeftTail - iLeftHead;
        int pRightHead = pLeftTail + 1;
        int pRightTail = pTail;
        TreeNode *root = new TreeNode(preorder[pHead]);
        root->left = doBuildTree(preorder, pLeftHead, pLeftTail, inorder, iLeftHead, iLeftTail);
        root->right = doBuildTree(preorder, pRightHead, pRightTail, inorder, iRightHead, iRightTail);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return doBuildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};