Given two arrays representing **In-order** and **Preorder** traversals of a binary tree, the task is to construct the tree and print "level-order" traversal.

##### Example 1: Construct Binary Tree from Preorder and In-order Traversal

Input : Inorder: **2,1,3**, Pre-order: **1,2,3**

Output : **1,2,3**

1 / \ 2 3

##### Example 2: Construct Binary Tree from Preorder and In-order Traversal

Input : Inorder: **4,2,5,1,3,6**, Pre-order: **1,2,4,5,3,6**

Output : **1,2,3,4,5,6**

1 / \ 2 3 / \ / 4 5 6

## Solutions

### Method 1: Recursion

In a Preorder traversal, the left-most element is the root of the tree.

By searching "root" in the Inorder traversal, we can find out all elements on the left side of "root" is in the left subtree and elements on right in the right subtree.

We recursively follow the above steps and construct the final tree.

preOrderIndex -> 0 constructTree(int[] inOrder, int[] preOrder, int inStart, int inEnd) if (inStart > inEnd) return null node -> new Node(preOrder[preOrderIndex++]) if (inStart == inEnd) return node divideIndex -> search(inOrder, inStart, inEnd, node.data) node.left -> constructTree(inOrder, preOrder, inStart, divideIndex - 1) node.right -> constructTree(inOrder, preOrder, divideIndex + 1, inEnd) return node search(int arr[], int start, int end, int value) i for (i = start; i <= end; i++) if (arr[i] == value) return i return i

##### Complexity

The time complexity of this solution is

**O(n**and space complexity is^{2})**O(n)**due to auxiliary stack.