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
profile
Contributed by
65 upvotes
Asked in companies
MicrosoftAppleInfosys

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.

Example

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.

Example

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?
Full screen
Console