**Objective:** **- **Given a inorder and preorder traversal, construct a binary tree from that.

**Input:** Inorder traversal and Depth-First-Search.

**Approach:**

**int**[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 };

**int**[] DFS = { 1, 2, 4, 8, 5, 3, 6, 7, 9 };

- First element in DFS
*[]* will be the *root* of the tree, here its 1.
- Now the search element 1 in
*inorder[]*, say you find it at position *i*, once you find it, make note of elements which are left to *i* (this will construct the leftsubtree) and elements which are right to *i* ( this will construct the rightSubtree).
- See this step above and recursively construct left subtree and link it root.left and recursively construct right subtree and link it root.right.
- See the picture and code.

Construct-a-Binary-Tree-from-Given-Inorder-and-Depth-First-Search

**Complete Code:**

**Output:**

inorder traversal of constructed tree :
8 4 2 5 1 6 3 7 9

*Related*