# 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.

For example, given the `preorder` and `inorder` traversal of a binary tree

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

Return the following binary tree:

```    3
/ \
9  20
/  \
15   7```

The solution approach for this problem is same as construct-binary-tree-from-inorder-and-postorder-traversal

As discussed above the preorder traversal follows `Root->Left->Right` order, that makes it very convenient to construct the tree from its root.

Let’s do it. The first element in the `preorder` list is a root. This root splits `inorder` list into left and right subtrees. Now one have to pop up the root from `preorder` list since it’s already used as a tree node and then repeat the step above for the left and right subtrees.

```class Solution {

private int root_index = 0;
private int[] preorder = null;
private int[] inorder = null;
private Map<Integer, Integer> inorderIndexMap = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int n = inorder.length;
for(int i = 0 ; i < n ; i++){
inorderIndexMap.put(inorder[i], i);
}
return buildTree(0, n-1);
}

private TreeNode buildTree(int l, int r){
if( l > r){
return null;
}
int root_val = preorder[root_index++];
TreeNode root = new TreeNode(root_val);
int inorderIndexOfRoot = inorderIndexMap.get(root_val);
root.left = buildTree(l, inorderIndexOfRoot-1);
root.right = buildTree(inorderIndexOfRoot+1, r);
return root;
}
}
```

Categories: Binary Tree