> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/construct-binary-tree-from-preorder-and-inorder-traversal.md).

# 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

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

Return the following binary tree:

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

```java
class Solution {
    public TreeNode helper(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd,
            HashMap<Integer, Integer> map) {
        if (preStart > preEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = map.get(preorder[preStart]);
        int leftLength = index - inStart;
        int rightLength = inEnd - index;
        root.left = helper(inorder, inStart, index - 1, preorder, preStart + 1, preStart + leftLength, map);
        root.right = helper(inorder, index + 1, inEnd, preorder, preEnd - rightLength + 1, preEnd, map);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // We can use map because it is given that : duplicates do not exist in the tree
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1, map);
    }
}
```