Construct a strict binary tree

Moderate
0/80
Average time to solve is 25m
10 upvotes
Asked in companies
OlaAmazon

Problem statement

You have been given an array/list of integers, let’s say ‘PRE’, which represents the preorder traversal of a strict binary tree and an array/list ‘TYPENL’ which has only two possible values either ‘L’ or ‘N’ where the value ‘L’ indicates that the corresponding node in Binary Tree is a leaf node and value ‘N’ indicates that the corresponding node is a non-leaf node.

You are supposed to construct a strict binary tree from the given two arrays/lists and return the root node of the constructed binary tree.

NOTE: 
A strict binary tree is a tree where each node has either 0 or 2 children.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ which denotes the number of nodes in the binary tree or the number of elements in the given arrays/lists.

The second line of each test case contains ‘N’ single space-separated integers denoting the preorder traversal of the binary tree, i.e. (‘PRE’).

The third line of each test case contains ‘N’ single space-separated characters with values either ‘L’ or ‘N’ denoting whether the corresponding node is a leaf or a non-leaf node (‘TYPENL’).
Output Format: 
For each test case, print a single line that contains space-separated characters for each node which can be either 'N' or 'L'.
Note: 
You don’t need to print anything, it has already been taken care of.
Constraints: 
1 <= 'T' <= 100
1 <= 'N' <= 3000
1 <= 'VAL' <= 10 ^ 5 

Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “VAL” is the value of the binary tree node.

Time Limit: 1 sec
Sample Input 1:
3
1
5 
L 
3
1 3 5
N L L 
7
2 4 8 5 1 9 3 
N N L L N L L
Sample Output 1:
5 
3 1 5 
8 4 5 2 9 1 3
Explanation of Sample Input 1:
For the first test case, we have 5 as the root node and inorder traversal of the strict binary tree is printed.

For the second test case, we have 1 as the root node and inorder traversal of the strict binary tree is printed.

For the third test case, we have 2 as the root node and inorder traversal of the strict binary tree is printed.
Sample Input 2:
2
7
1 2 2 5 4 1 2 
N N L L N L L 
7
7 6 3 5 4 2 1 
N N L L N L L
Sample Output 2:
2 2 5 1 1 4 2 
3 6 5 7 2 4 1
Explanation of Sample Input 2:
For the first test case, we have 1 as the root node and inorder traversal of the strict binary tree is printed.

For the second test case, we have 7 as the root node and inorder traversal of the strict binary tree is printed.
Hint

Create a node and start linking the left and right subtrees of each node.

Approaches (1)
Recursive Approach

Our approach is to take account of the properties of a strict binary tree and accordingly apply the same for assigning the left and right child of a particular node in a binary tree. All we need to do is to is recursively apply the properties to both left and right subtrees of a binary tree.

 

The steps are as follows:

 

  1. As we know the first element in ‘PRE’ will always be root because it is the preorder traversal of a binary tree. So we can easily figure out the root node.
  2. Now, If the left subtree is empty, then the right subtree must also be empty because of the property of the strict binary tree containing either 0 or 2 children. And for that case, the ‘PRELN’[] entry for root must be ‘L’ and we can simply create a node and return it.
  3. Now if left and right subtrees are not empty, then we recursively call for left and right subtrees and link the returned nodes to root.
Time Complexity

O(N), where ‘N’ is the number of elements in the given arrays/lists.

 

Traversing for left and right boundaries in a binary tree takes linear time. Also, traversing for leaf nodes can also be performed in linear time. So the overall time complexity will be O(N).

Space Complexity

O(log N), where ‘N’ is the number of elements in the given arrays/lists.

 

The recursion stack can grow to the maximum height of the binary tree. Here we are considering a strict binary tree (Having 0 or 2 children) whose maximum height will be log N. So the overall space complexity will be O(log N).

Code Solution
(100% EXP penalty)
Construct a strict binary tree
Full screen
Console