**Introduction**

Binary Trees has been a favorite topic of many companies, including Amazon, Google, Microsoft, etc. Usually, the problems on Binary Trees look very complicated, but it seems pretty easy to solve when we look at its solution.

Why is that so? This is because the topic binary trees require a stronghold over recursion and some visualization.

To help you solve binary tree problems, we will discuss a common problem, i.e., Construct a Binary Tree from a given Preorder and Inorder traversal. This problem has been asked in many interviews and tests your thought process about approaching binary tree problems.

Let’s look at the problem first.

We are given 2 sequences of size N, i.e., the number of nodes in the binary tree. The first sequence is the pre-order traversal of the binary tree and the second sequence is the in-order traversal of the binary tree. Your task is to construct a Binary Tree from a given Preorder and Inorder traversal. Return the reference or the pointer to the root of the binary tree.

** Pre-order Sequence : **1 2 4 5 3 6

** In-order Sequence : **4 2 5 1 6 3

__Output Binary Tree__:

Return the pointer or reference to the root containing the value 1.

**Approach**

Let’s understand how we got to the output binary tree before jumping to the approach.

** Pre-order Sequence : **1 2 4 5 3 6

** In-order Sequence : **4 2 5 1 6 3

Now, we know that a pre-order sequence can be recursively defined as:

**{Root, Elements of left subtree, Elements of right subtree}**

and, an in-order sequence can be recursively defined as:

**{Elements of left subtree, Root, Elements of right subtree}**

So using the above pre-order definition, we can find the root first, the first element in the sequence. Hence root is 1.

If 1 is the root of the binary tree, then using the in-order definition, elements to the left will be present in the left subtree, and elements to the right will be present in the right subtree with root as 1, respectively.

So we can understand the above explanation using the following illustration:

Now, suppose we use the pre-order and in-order recursive definitions and apply them on the left and right subtrees in the illustration above. In that case, we can understand the following process using the illustration given below:

So we have reached the condition that each subtree now has at most a single element. Hence we can replace the subtrees as nodes with values of each subtree.

I hope you got the essence of the question from the above example. If not, then no worries, we will discuss the approach here.

If you look, how we Construct a Binary Tree from a given Preorder and Inorder traversal, you will get a sense of how the binary tree is constructed using the traversal sequences given to us.

If one tries to observe, the first thing we have done is finding the root first. After finding the root, we can now split the traversals into 3 parts, the left subtree, the root, and the right subtree, respectively.

We recursively follow the same procedure, i.e., finding root nodes of respective subtrees, splitting into 3 parts further, and repeating the same process.

Now when should we terminate? We terminate when we are left with 0 or, at most, a single element in each subtree.

We have understood how we identify repetitive work, asking recursion to do the same for us and finally returning the reference to the root.

So **approach** can be formulated as:

- Find the root node using the pre-order traversal.
- Find the left subtrees and the right subtrees using in-order traversal by finding the index of the root node of respective subtrees.
- Once the root node is found, we can recurse down on the left and right subtrees, i.e., left subarray, and right subarray split at respective root index to repeat the same process until we find at most a single element in either sub-array.