Given a binary tree. Your task is to print the bottom right view of the binary tree.
Bottom right view, on viewing the given binary tree at the angle of 45 degrees from the bottom right side.
For Example
In the above binary tree, only node { 4, 5, 6 } is visible from the bottom right only node ‘1’ and node ‘3’ are hidden behind node ‘6’.
node ‘2’ is hidden behind node ‘5’.
Input Format
The first line contains an integer 'T' which denotes the number of test cases. Then the test cases are as follows.
The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree depicted in the above image would be :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
Note
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format
For each test case, print the array of the values of visible nodes.
There can be multiple orders to arrange the node’s value which is visible from the bottom-right so return sorted order (ascending order).
Print the output of each test case in a new line.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraint
1 <= T <= 100
1 <= N <= 3000
-10^9 <= data <= 10^9 (data != -1)
Where ‘N’ is the number of nodes in the tree and ‘data’ denotes data contained in the node of a binary tree.
Time Limit: 1 sec
CodingNinjas
author
2y
Diagonal Traversal
Assign a level to every diagonal.
Return the last node’s value of every level.
You can solve this problem with diagonal traversal, To know more about ‘diagonal level traversal’ follow the link.
Algorithm
Create an ‘answer’ array, to store the answer for the return part.
Assign a ‘maxLevel=0’, to track already visited max level.
Use the recursion function ‘brViewUtil( root, level)’
It takes the two-parameter root and level.
Where ‘root’ is the current node, and level is basically the level of ‘root’ according to the above image.
Call the ‘brViewUtil( root->right, level)’
If the ‘root’ is at level ‘x’ and ‘x >= maxLevel’ then the root is the last node of level ‘x’ so add it into ‘answer’ array and update ‘maxLevel=level’.
Call the ‘brViewUtil( root->left, level+1)’
In this step call the same function with one greater level.
Example - node ‘1’ has ‘level=0’ so it’s left node ‘2’ has ‘level=2’. That’s why in every left call, the level will increase by ‘1’ compared to its parent node level.
In the end, sort (ascending order) the ‘answer’ array and return.
Space Complexity: O(n)Explanation:
O(N), Where ‘N’ is the number of nodes in a binary tree.
We are using a size of ‘H’(height of the binary tree) call stack and an extra array ‘answer’ which can be possible of size ‘N’.
Time Complexity: O(n)Explanation:
O(N), Where ‘N’ is the number of nodes in a binary tree.
We are traversing every node at max once.
Help your peers!
Add answer anonymously...
Top Paytm Software Developer interview questions & answers
