# Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

## Recursion

```
Pre-order: F, B, A, D, C, E, G, I, H
p
In-order: A, B, C, D, E, F, G, H, I
q
```

From first char `F`

in `Pre-order`

, we are sure that the root of the tree is `F`

.

and from `In-order`

, `F`

divide the tree into two parts, the left one is `A, B, C, D, E`

, the right one is `G, H, I`

.

```
F
/ \
A, B, C, D, E G, H, I
```

`A, B, C, D, E`

and `B, A, D, C, E`

become a new `buildTree`

problem. so we can build the tree recursively.
the result tree is the left children of `F`

.

Similarly, `G, H, I`

and `G, I, H`

become the right children of `F`

.

### Source code *Read on Github*

```
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11
12 int p = 0;
13 int[] preorder;
14 int[] inorder;
15
16
17 TreeNode buildTree(int st, int ed){
18
19 if(st >= ed) return null; //
20
21 TreeNode root = new TreeNode(preorder[p]);
22
23 int i;
24 for(i = st ; i< ed && inorder[i] != preorder[p] ; i++);
25
26 p++;
27 root.left = buildTree(st, i);
28 root.right = buildTree(i + 1, ed);
29
30 return root;
31 }
32
33
34 public TreeNode buildTree(int[] preorder, int[] inorder) {
35 // Note: The Solution object is instantiated only once and is reused by each test case.
36
37 this.preorder = preorder;
38 this.inorder = inorder;
39 this.p = 0;
40 //if (preorder.length == 0) return null;
41 return buildTree(0 , inorder.length);
42 //return new TreeNode(preorder[p]);
43 }
44 }
```