Last Updated: 14 Dec, 2020
Construct Tree From Preorder Traversal
Moderate
Asked in companies
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
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
Approaches
- 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.
- 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.
- Then we traverse the array and if the element is a leaf node, we create a new node and simply push it in the stack.
- Otherwise if it is not a leaf node , we create a leaf node and if the stack is not empty, we see if the left os the stack is NULL or not, If null we make the new node and connect it with the left pointer of the top of the stack.
- Otherwise, we connect it to the right pointer of the top of the stack and pop the top element from the stack as it now has 2 children.
- 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’
- Then we traverse the ‘pre’ array and if root nod does not exist thenwwe create it. And push it in the stack.
- Then for every node we check if it is a leaf or not. If it is a leaf, we just create it and push it in the stack.
- Otherwise if it is not a leaf node , we create a leaf node and if the stack is not empty, we see if the left os the stack is NULL or not, If null we make the new node and connect it with the left pointer of the top of the stack.
- Otherwise, we connect it to the right pointer of the top of the stack and pop the top element from the stack as it now has 2 children.
- Finally, we return the root node.