# Construct Binary Tree from Preorder and Inorder Traversal

## Problem

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

## Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

      2
/ \
1   3

## Note

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

## Code - Java

/**
* Definition of TreeNode:
* public class TreeNode {
*   public int val;
*   public TreeNode left, right;
*   public TreeNode(int val) {
*     this.val = val;
*     this.left = this.right = null;
*   }
* }
*/
public class Solution {

private int preIndex = 0;

/**
* @param preorder : A list of integers that preorder traversal of a tree
* @param inorder  : A list of integers that inorder traversal of a tree
* @return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, inorder, 0, inorder.length);
}

private TreeNode build(int[] preorder, int[] inorder, int start, int end) {
if (preIndex >= preorder.length) {
return null;
}

int v = preorder[preIndex++];
TreeNode node = new TreeNode(v);

int i;
for (i = start; i <= end; i++) {
if (inorder[i] == v) break;
}

if (i > start) {
node.left = build(preorder, inorder, start, i - 1);
}

if (i < end) {
node.right = build(preorder, inorder, i + 1, end);
}

return node;
}
}