Construct Binary Tree From In-order and Level-order.

Hard
0/120
profile
Contributed by
10 upvotes
Asked in companies
IntuitJ P Morgan India PVT ltd

Problem statement

You are given two arrays, ‘inOrder’ and ‘levelOrder’, representing the in-order and level-order traversal of a binary tree, respectively. Your task is to construct the binary tree from the given in-order and level-order traversals.

For Example:

You are given ‘inOrder’ = {4, 2, 5, 1, 3, 6} and ‘levelOrder’ = {1, 2, 3, 4, 5, 6}. The binary tree constructed from given traversals will look like this:

tree1

The inorder traversal of the above tree will be { 4, 2, 5, 1, 3, 6 }.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.

The next line of each test case contains ‘N’ single space-separated integers, representing the in-order traversal of the Binary Tree.

The next line of each test case contains ‘N’ single space-separated integers, representing the level-order traversal of the Binary Tree.
Output Format: 
For each test case, print the inorder traversal of the binary tree.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 2000
0 <= inOrder[i] <= 10^5
0 <= levelOrder[i] <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
6
4 2 5 1 3 6
1 2 3 4 5 6
5
1 2 3 4 5
4 2 5 1 3
Sample Output 1:
4 2 5 1 3 6
1 2 3 4 5
Explanation of Sample Input 1:
Test Case 1: The binary tree constructed from given traversals will look like this:

tree1

The inorder traversal of the above tree will be {4, 2, 5, 1, 3, 6}.

Test Case 2: The binary tree constructed from given traversals will look like this:

tree2

The inorder traversal of the above tree will be {1, 2, 3, 4, 5}.
Sample Input 2:
2 
3
1 2 3
2 1 3
1
2
2
Sample Output 2:
1 2 3
2
Hint

Think of finding the position for every element in the tree.

Approaches (2)
Recursion

Prerequisite: In-order and level-order traversal of a tree.

 

The basic is to find the root and recursively construct the left and right subtrees. The first element of the ‘LEVELORDER’ traversal will always be the root. We then find the position of the root in ‘INORDER’. As we know that in inorder traversal, we first travel the left child, then the root, and then the right child. So, we can say that the elements before the root in ‘INORDER’ will lie in the left subtree of the root, and elements after the root in the ‘INORDER’ will lie in the right subtree of the root.

 

In the same way, we will recursively create the left subtree and the right subtree.

 

 

Algorithm :

  • Initialize a TreeNode ‘ROOT’ and set it to null.
  • Return ‘BUILDTREEHELPER’(‘ROOT’, ‘LEVELORDER’, ‘INORDER’, 0, ‘N’- 1).

 

Maintain a function ‘BUILDTREEHELPER’(NODE, LEVELORDER, INORDER, INSTART, INEND);

  • If ‘INSTART’ is less than ‘INEND’, return NULL.
  • If ‘INSTART’ is equal to ‘INEND’, return a new TreeNode with the value ‘INORDER[INSTART]’.
  • Initialize a boolean variable ‘FOUND’ with value false.
  • Initialize a variable ‘INDEX’ with value 0.
  • Iterate 'I' in 0 to 'LEVELORDER.LENGTH':
    • Initialize a variable 'DATA' with value 'LEVELORDER[I]'.
    • Iterate 'J' in 'INSTART' to 'INEND'
      • If 'DATA' equal to 'INORDER[J]':
        • Initialize 'NODE' with value 'DATA'.
        • Set 'INDEX' to 'J'
        • Set 'FOUND' to true.
        • Break.
    • If 'FOUND' is true. Break.
  • Recursively create left subtree. Set ‘NODE.LEFT’ as ‘BUILDTREEHELPER’(‘NODE’, ’LEVELORDER’, ‘INORDER’, ‘INSTART’, ‘INDEX’ - 1)).
  • Recursively create the right subtree. Set ‘NODE.RIGHT’ as ‘BUILDTREEHELPER’(‘NODE’, ‘LEVELORDER’, ‘INORDER’, ‘INDEX’ + 1, ‘INEND’));
  • Return 'NODE'.
Time Complexity

O(N ^ 3), where ‘N’ is the number of nodes in the tree.

 

For every element in ‘INORDER’, we are traversing ‘LEVELORDER’, then for every element in ‘LEVELORDER’, we are traversing from ‘INSTART’ to ‘INEND’. Hence the total time complexity is O(N ^ 3).

Space Complexity

O(N), where ‘N’ is the number of nodes in the tree.

 

The recursive stack can contain at most ‘N’ nodes of the binary tree. Hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Construct Binary Tree From In-order and Level-order.
Full screen
Console