Left Right Print

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
6 
5 3 9 4 2 1
0 1 2 3 4 -1 5 -1 -1 -1 -1 -1 -1
Sample Output 1 :
4 1 2 3 9 5
Explanation Of Sample Input 1 :
For the first case:
The tree generated from the edges is:


Starting from the last level printing the leftmost value then the rightmost value we get 4 1 2 3 9 5.
So the final output is [4, 1, 2, 3, 9, 5].
Sample Input 2 :
2
3
1 2 3
0 1 2 -1 -1 -1 -1
2
5 11
0 -1 1 -1 -1
Sample Output 2 :
2 3 1
11 5
Hint

Can you think of any way to store the values of nodes level-wise and then print it?

Approaches (1)
Breadth-First Search

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

  1. Declare a queue 'Q' to perform the BFS.
  2. Push the root node into the queue.
  3. Declare a 2d matrix 'levelValues' to store the values of nodes level-wise.
  4. 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.
  5. Reverse the ‘levelValues’ matrix to get the last level on the top.
  6. Declare an array 'ANS' to store the final contents of the array.
  7. 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.
  8. Return the 'ANS' array.
Time Complexity

O( N ), Where ‘N’ denotes the number of nodes in the tree.  

 

BFS visits each node only once hence the time complexity for BFS is O( N ). Printing the values of the nodes level-wise also visits each node only once. Hence the time complexity to print is also O( N ).

Hence the time complexity is O( N ).

Space Complexity

O( N ), Where ‘N’ is the number of nodes.

 

Since the tree is a binary tree so adjacency list for each node will be of size at most 2. Hence the space complexity for the ‘TREE’ matrix is  O( N ). The space complexity for ‘levelValues’ and ‘ANS’ array is also O( N ) because it stores each node only once.

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Left Right Print
Full screen
Console