# Construct Binary Tree from Preorder and Inorder Traversal

#1

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```

#2

The below algorithm iteratively builds the tree by using a stack and a map to identify a value’s position in `inorder` traversal.

``````type Stack []*TreeNode
func (s *Stack) Push(n *TreeNode) {
*s = append(*s, n)
}
func (s *Stack) Pop() (n *TreeNode) {
x := s.Len() - 1
n = (*s)[x]
*s = (*s)[:x]
return
}
func (s *Stack) Len() int {
return len(*s)
}
func (s *Stack) Peek() *TreeNode {
x := s.Len() - 1
return (*s)[x]
}
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder)==0 || len(inorder)==0{ return nil}
inOrderMap := make(map[int]int)
for i, v := range inorder{
inOrderMap[v] = i
}
stack := Stack{}
root := &TreeNode{Val: preorder[0]}
stack.Push(root)
for i:=1;i<len(preorder);i++{
val := preorder[i]
node := &TreeNode{Val : val}
if inOrderMap[val] < inOrderMap[stack.Peek().Val]{
stack.Peek().Left = node
} else {
var parent *TreeNode
for stack.Len()!=0 && inOrderMap[val] >inOrderMap[stack.Peek().Val]{
parent = stack.Pop()
}

parent.Right = node
}
stack.Push(node)
}

return root
}
``````

#3

A recursive approach in Java.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> im = new HashMap<>();
for(int i=0;i<inorder.length;i++){
im.put(inorder[i], i);
}
return helper(0, 0, inorder.length-1, preorder, inorder, im);
}

public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder, Map<Integer, Integer> im){
if(preStart > preorder.length-1 || inStart>inEnd){return null;}
TreeNode node = new TreeNode(preorder[preStart]);
int inIndex = im.get(preorder[preStart]);
node.left = helper(preStart+1, inStart, inIndex-1, preorder, inorder, im);
node.right = helper(preStart+inIndex-inStart+1, inIndex+1, inEnd, preorder, inorder, im);
return node;
}
}
``````