## Introduction

Solving problems based on a particular topic repeatedly until you have completely understood all the aspects of the topic is an excellent way of learning. There are multiple problems based on the__ Binary tree__ that can help you completely understand its properties.

This blog will discuss one frequently asked question based on binary trees in coding interviews. The problem we will discuss is a variation of the problem known as Construct a Binary Tree from a given Preorder and Inorder traversal, and we will also discuss the working of this problem, and then we will focus on our current problem.

## Problem Statement

We will be given the two arrays or vectors, let's assume arrays for now, ‘array1’, and ‘array2’, of size ‘N’, in which ‘array1’ contains the preorder traversal of a tree, and ‘array2’ has the inorder traversal of a tree. Our task is to find if we can construct a binary tree using a preoder and an inorder array.

In a tree, if a parent node has at most 2 children, then the tree is known as a binary tree. When validating the given arrays, we must keep this binary tree property in mind.

As we have mentioned earlier, the problem we are currently discussing is a variation of another problem. In the main problem, our task is to construct a binary tree using the preoder and inorder traversals given to us in the form of an array. But here, our goal is to check whether the given preorder and inorder array are valid for any binary tree without actually constructing a tree. In short, we cannot create a binary tree with given inputs; we must look for another way.

But it is best to discuss the working of the main problem because it will give us the logic to implement the solution for our current problem. The logic we will use in our current problem is similar to the logic of the main problem. We need to add some conditions to the current problem.

### Example

**You can use an array or vector to store the inorder and preorder **tree traversal**.**

**Input:** Inorder Array and Preorder Array are given as input,

Preorder[] = [10,20,40,50,30]

Inorder[] = [40,20,50,10,30]

In the case of Inorder traversal, we traverse the tree following this pattern:

**Left****Root**-
**Right**

In the case of Preorder traversal, we traverse the tree following this pattern:

**Root****Left**-
**Right**

If the Preorder traversal of the tree is given, the first element in the traversal will always be the root. So in our example, where the preorder array is,

Preorder[] = [10,20,40,50,30],

**The root is 10. **

But with the help of only preorder traversal alone, we need help understanding which elements lie in the root's left and right subtree. So we need to make use of the inorder array.

Inorder[] = [40,20,50,10,30]

Element 10 lies in the third index of the inorder array. So therefore, everything to the left of 10 (i.e., from index 0 to 2) should lie in the left subtree of 10. Similarly, everything to the right of 10 in the array (i.e., index 4) should lie in the right subtree.

But how will we know the root of the left and right subtrees? We have to look at the next element in the preorder traversal array. The next element in the preorder traversal array is the root of the left subtree (if the left subtree exists).

The next element in the preorder traversal array is 20.

Preorder[] = [10,20,40,50,30].

Therefore the root of the left subtree is 20.

Now to know what comes in the left and right subtree of 20, we again take the help of an inorder traversal array.

Inorder[] = [40,20,50,10,30]

20 lies in index 1 and elements to the left of it lie in the left subtree, and the element to its right lies in the right subtree. So 40 should be the left child, and 50 should be the right child of 20.

Now that we are done with the entire left subtree let’s build the right subtree. As element 30 is the only node left, it connects to root 10.

Our final constructed binary tree is:

While building the tree, we can notice a recursive pattern in the above steps, and we can then follow all the steps to construct the tree.

We are doing a preorder traversal of the tree and building the tree with the help of the inorder array.

You can check out the __Construct a Binary Tree from a given Preorder and Inorder traversal__ blog for implementation of the above approach.

Now that we have understood the problem statement let's talk about how to solve this problem.

Also Read About, __Binary Tree Postorder Traversal____.__