Construct Tree From Preorder Traversal

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
OracleAmazonCodenation

Problem statement

Given an array ‘pre[]’ of ‘n’ elements that represent Preorder traversal of a spacial binary tree where every node has either 0 or 2 children. Also Given a boolean array ‘isLeaf’ such that isLeaf[i] represents if the ‘i-th’ node in the ‘pre’ array is a leaf node or not. Write a function to construct the tree from the given two arrays and return the head node of the constructed binary tree.

For example let pre={1,2,4,5,3,6,7}

isLeaf={0,0,1,1,0,1,1}

Here 0 means that the node is not a leaf node and 1 means that the node is a leaf node.

Then we will have the following tree

alt-1

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The First line of each test case contains the integer ‘n’ denoting the number of elements in the binary tree.

The second of each test case line contains n space-separated integers denoting the value of the node of the binary tree.

The third line of each test case contains n space-separated integers each being 0 or 1. Here 0 means that the node is not a leaf node and 1 means that the node is a leaf node.
Output Format 
For each test case, return the root node of the constructed tree.

Output for each query must be printed in a new line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^3
-10^9 <=pre[i] <=10^9  

Where ‘T’ is the total number of test cases and N denotes the number of elements in the ‘pre’ and the ‘isLeaf’ array and ‘pre[i]’ denotes the range of values for any element inf the ‘pre’ array.

Time limit: 1 sec
Sample Input 1:
2
5
10 30 20 5 15
0 0 1 1 1
9
2 3 5 15 11 6 4 7 9
0 0 0 1 1 1 0 1 1
Sample Output 1:
20 30 5 10 15
15 5 11 3 6 2 4 7 9
Explanation of sample input 1 :
Test Case 1:

We can clearly see that 10 and 30 are not leaf nodes and rest of the nodes are leaf nodes. Therefore,

The Tree is:

tree 10

We can verify that the pre order traversal of the tree is { 20 30 5 10 15} and all the nodes satisfy the condition of the ‘isLeaf ‘ array and therefore the constructed tree is correct.

The pre-order traversal of this tree is: { 10 30 20 5 15} which matches the given input.

Test Case 2:
We can clearly see that 2. 3,5, 5, are not leaf nodes and rest are leaf nodes
The tree is:

tree-big

We can verify that the pre order traversal of the tree is {2 3 5 15 11 6 4 7 9} and all the nodes satisfy the condition of the ‘isLeaf ‘ array and therefore the constructed tree is correct.

The in-order traversal of the above tree is: {15 5 11 3 6 2 7 4 9}
Sample Input 2:
2
7
1 2 3 4 5 6 7
0 0 0 1 1 1 1
5
21 35 6 7 8
0 1 0 1 1
Sample Output 2:
4 3 5 2 6 1 7 
35 21 7 6 8
Hint

Construct the tree recursively

Approaches (2)
Recursive Approach
  • The idea is to construct the tree node by node.
  • Take the first element of the ‘pre[]’ array. Now it is guaranteed that this will be the root node because of the definition of pre-order traversal.
  • Now for any node, if ‘isLeaf’ is true it means that it is a leaf node. In this case, we create the node and return it.
  • Otherwise, since the binary tree has no children or 2 children, we recursively call the function to build the left and right  subtree of the current node
  • We recursively make the tree for the left and the right children in the same way.
  • In the end, we return the root node.

Keeping in mind the above idea, we can devise the following recursive  approach:

  • We define a function helper which takes the ‘pre’ array ‘isLeaf’ and a variable ‘curIdx’ to keep track of the current index.
  • The base case will be if we completely traverse the array i.e when ‘curIdx’ is equal to the size of ‘pre’ array then we return NULL.
  • Otherwise, we create a node temp and add it to our tree. If it is not a leaf, we recursively calculate the left and the right subtrees.
  • Finally, we return the root node.
Time Complexity

O(n), where ‘n’ is the number of elements in the ‘pre’ array.

 

We need to visit each node of the ‘pre’ array to completely make the tree. Therefore the complexity is the order of n.

Space Complexity

O(n), where ‘n’ is the number of elements in the ‘pre’ array

 

Stack takes space for recursive calls of the order ‘n

Code Solution
(100% EXP penalty)
Construct Tree From Preorder Traversal
Full screen
Console