Last Updated: 9 Jul, 2022

Left Right Print

Moderate

Solve now

Problem statement

You are given the root of a binary tree. Print the values of the tree in the following way:

i. Print the values of nodes of the last level in this way: print the leftmost value then the rightmost value and continue until all the values of nodes of the last level are printed.

ii. Do the same for the second last level then the third last level until the first level.

There are total ‘N’ nodes, nodes are numbered from 0 to ‘N’-1. The values of nodes are given by an array ‘NUMS’, Where ‘NUMS[ i ]’ = the value of the ‘i’th node. You are also given the level order traversal of the tree in an array ‘SEQUENCE’. ‘SEQUENCE[ i ]’ = -1 denotes a null node.

Example:

Input: ‘N’ = 3,  ‘NUMS’ = [1, 2, 3], ‘SEQUENCE’ = [0, 1, 2, -1, -1, -1, -1].

Output: [2, 3, 1]
Printing the last level as the leftmost value then the rightmost value we get = 2, 3
Printing the 2nd last level we get = 1
Hence, the final array is: [2, 3, 1].

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains one integers ‘N’ where ‘N’ denotes the length of the array ‘NUMS’.

The second line of each test case contains ‘N’ integers.

The third line of each test case contains ‘2*N+1’ integers.

Output format :

For each test case, you don’t need to print anything just return the resultant array.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
Sum of ‘N’ <= 10^5
1 <= NUMS[i] <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, We can do a bfs to store the values of the nodes level-wise in a matrix in which the row represents a level and the column represents the values in that level. Since the bfs explore the nodes from the first level then the second level and so on. We need to reverse the rows of the matrix. After reversing the matrix iterate over all the rows and print the values as per the rule.

The steps are as follows:-

Function leftRightPrint(int n, int m, vector<int>& nums, vector<vector<int>>& edges):

Declare a queue 'Q' to perform the BFS.
Push the root node into the queue.
Declare a 2d matrix 'levelValues' to store the values of nodes level-wise.
Run a loop while 'Q' is not empty.
- Initialize a variable 'curSize' with the current size of the 'Q'.
- Declare an array 'curValues' to store the values of the current level.
- Run a loop from 'i' = 0 to ‘curSize’-1.
  - Initialize a variable 'SRC' with the value of the front element of the 'Q'.
  - Pop out the front element of the 'Q'.
  - Initialize a variable 'VAL' with the value of the node 'SRC'.
  - Append the variable 'VAL' into the 'curValues' array.
  - Append the left and right child of the node 'SRC' into the 'Q'.
- Append the array 'curValues' into the ‘levelValues’ matrix.
Reverse the ‘levelValues’ matrix to get the last level on the top.
Declare an array 'ANS' to store the final contents of the array.
Iterate over the 'levelValues' matrix level-wise.
- Initialize a variable 'totalNodesAtL' with the size of the columns of 'levelValues' in the 'ith' row.
- Run a loop, for j = 0 to 'totalNodesAtL'/2.
  - Append the value of 'levelValues' matrix at 'ith' row and 'jth' column (leftmost) then append the value at 'ith'row and ('totalNodeAtL' - 1 - 'j')th column (rightmost) into the ‘ANS’ array.
  - If the 'totalNodesAtL' is odd then the middle value needs to be appended separately.
Return the 'ANS' array.

Solve now