# Reconstruct binary tree from in-order and pre-order

The problem statement:

Given two integer arrays representing the in-order and pre-order traversals of a binary tree, reconstruct the binary tree.

This problem seems easier using recursion. The idea is that the pre-order can tell us what the root is and the in-order what its left and right children are. A first attempt might iterate through the in-order traversal and find the root from the pre-order traversal. However we can use a shortcut. The pre-order traversal places the root first, then the left sub-tree and then the right sub-tree. Therefore if we construct the left sub-tree first we don't need to use a loop to find the root. It will simply be the earliest element of the pre-order traversal that we have not used.

```class Solution {
Map<Integer, Integer> inorderIndex = new HashMap<>();
int preorderPointer;
int[] preorder;

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

this.preorderPointer = 0;
this.preorder = preorder;

return this.buildTreeInner(0, preorder.length - 1);
}

public TreeNode buildTreeInner(int leftPointer, int rightPointer) {
if (leftPointer > rightPointer) {
return null;
}

int rootVal = this.preorder[this.preorderPointer];
TreeNode root = new TreeNode(rootVal);
int rootIndex = this.inorderIndex.get(rootVal);

this.preorderPointer++;
root.left = this.buildTreeInner(leftPointer, rootIndex - 1);
root.right = this.buildTreeInner(rootIndex + 1, rightPointer);

return root;
}
}
```