Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Construct Binary Tree From Inorder and Preorder Traversal

Easy
0/40
Average time to solve is 10m
Contributed by

## 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 )
##### Sample Input 1:
``````5
1 2 4 7 3
4 2 7 1 3
``````
##### Sample Output 1:
``````1 2 3 4 7

1 2 3
``````
##### Explanation of Sample Input 1:
``````The tree after the construction is shown below.
``````

##### Sample Input 2:
``````2
1 2
2 1
``````
##### Sample Output 2:
``````1 2
``````
##### Constraints:
``````1 <= N <= 3000
1 <= data <= 10^4

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

Time Limit: 1sec
``````
##### Follow-up:
``````Can you solve this in O(N) time complexity?
``````
Console