Last Updated: 23 Nov, 2020

Construct a strict binary tree

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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:

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

Solve now