 New update is available. Click here to update.

# Construct Binary Tree From Inorder and Preorder Traversal

Contributed by
Arshit Babariya
Last Updated: 23 Feb, 2023
Easy 0/40
Avg time to solve 10 mins
Success Rate 90 % Share 32 upvotes

## Problem Statement

#### You have been given the preorder and inorder traversal of a binary tree. Your task is to construct a binary tree using the given inorder and preorder traversals.

##### Note:
``````You may assume that duplicates do not exist in the given traversals.
``````
##### For example :
``````For the preorder sequence = [1, 2, 4, 7, 3] and the inorder sequence = [4, 2, 7, 1, 3], we get the following binary tree.
`````` Detailed explanation ( Input/output format, Notes, Images ) ##### Constraints:
``````1 <= T <= 100
1 <= N <= 3000
1 <= data <= 10^4

Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.

Time Limit: 1sec
``````
##### Sample Input 1:
``````3
5
1 2 4 7 3
4 2 7 1 3
2
1 2
2 1
3
1 2 3
2 1 3
``````
##### Sample Output 1:
``````1 2 3 4 7
1 2
1 2 3
``````
##### Explanation of Sample Input 1:
``````For the first test case, the tree after the construction is shown below.
`````` ``````For the second test case, the level order of the constructed tree is [1, 2]. The tree after the construction is shown below.
`````` ``````For the third test case, the level order of the constructed tree is [1, 2, 3]. The tree after the construction is shown below.
`````` ##### Sample Input 2:
``````2
3
1 2 3
3 2 1
1
7
7
``````
##### Sample Output 2:
``````1 2 3
7
``````  Auto Console