Last Updated: 9 Nov, 2021

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

Hard

Asked in companies

Solve now

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 }.

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

Solve now

Approaches

01 Approach

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'.

Solve now

02 Approach

In this approach, we will use a HashSet, ‘SET’ to reduce the time complexity from O(N ^ 3) to O(N ^ 2). The basic idea will be the same; we will find the root and recursively construct the left and right subtrees. The root will be the first element of ‘LEVELORDER’ and 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.

We will put the elements of the left subtree in the ‘SET’. Now, we will traverse the ‘LEVELORDER’ and if the current element of the ‘LEVELORDER’ is present in the ‘SET’ we will add it to ‘LEFTLEVEL’ otherwise we will add it to ‘RIGHTLEVEL’. We can check in constant time whether any element is present in ‘SET’ or not.

Now, we will use ‘LEFTLEVEL’ to create the left subtree and ‘RIGHTLEVEL’ to create the right subtree.

Algorithm :

Return ‘BUILDTREEHELPER’(‘LEVELORDER’, ‘INORDER’, 0, ‘N’ - 1, ‘N’).

Maintain a function ‘BUILDTREEHELPER’(‘LEVELORDER’, ‘INORDER’, ‘INSTART’, ‘INEND’, ‘N’).

If 'N' is less than 0, return null.
Initialize a TreeNode 'ROOT' with value 'LEVELORDER[0]'.
Initialize a variable 'INDEX' with value -1.
Iterate 'I' in 'INSTART' to 'INEND' to find the index of 'ROOT' in 'INORDER':
- If 'ROOT.DATA' is equal to 'INORDER[I], set 'INDEX' as 'I' and break.
Initialize a HashSet 'SET'.
Iterate 'I' in 'INSTART' to 'INDEX'.
- Add 'INORDER[I]' to 'SET'.
Initialize an array 'LEFTLEVEL' of size 'SET.SIZE'.
Initialize an array 'RIGHTLEVEL' of size 'INEND' - 'INSTART' - 'SET.SIZE'.
Initialize variables 'LEFT' and 'RIGHT' with value 0.
Iterate 'I' in 1 to 'N':
- If 'SET' contains 'LEVELORDER[I]', set 'LEFTLEVEL[LEFT++]' as 'LEVELORDER[I]'.
- Otherwise set 'RIGHTLEVEL[RIGHT++]' as 'LEVELORDER[I]'.
Recursively create left subtree. Se ‘ROOT.LEFT’ to ‘BUILDTREEHELPER’(‘LEFTLEVEL’,’ INORDER’, ‘INSTART’, ‘INDEX’ - 1, ‘INDEX’ - ‘INSTART’).
Recursively create left subtree. Se ‘ROOT.RIGHT’ to ‘BUILDTREEHELPER’(‘RIGHTLEVEL’, ‘INDEX’ + 1, ‘INEND’, ‘INDEX’ - 1, ‘INEND’ - ‘INDEX’).
Return ‘ROOT’.

Solve now