Bottom Right View of Binary Tree

Easy
0/40
Average time to solve is 10m
profile
Contributed by
14 upvotes
Asked in companies
DunzoSamsungAmdocs

Problem statement

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

alt text

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’.
Detailed explanation ( Input/output format, Notes, Images )
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.

tree

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
Sample Input 1
2
1 2 3 -1 4 -1 5 -1 -1 -1 -1
1 2 3 4 -1 5 -1 -1 -1 -1 6 -1 -1
Sample Output 1
 4 5
 3 4 6
Explanation Of Sample Input 1
Test Case 1: node ‘{ 4, 5 }’ is visible from the bottom right only node ‘1’ and node ‘3’ are hidden behind node ‘5’.
node ‘2’ is hidden behind node ‘4’.
Hence return { 4, 5 }.

alt text

Test Case 2:  node ‘{ 4, 3, 6 }’ is visible from the bottom right only node ‘2’ and node ‘5’ are hidden behind node ‘6’.
node ‘1’ is hidden behind node ‘3’.
Hence return { 3, 4, 6 } because is sorted (acending) order of { 4, 3, 6 }.

alt text

Sample Input 2
2
1 2 3 -1 -1 -1 -1
1 2 -1 3 -1 -1 -1
Sample Output 2
 2 3
 1 2 3
Hint

Try to traverse in a diagonal manner.

Approaches (1)
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.
Time Complexity

O(N), Where ‘N’ is the number of nodes in a binary tree.

 

We are traversing every node at max once.

Space Complexity

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

Code Solution
(100% EXP penalty)
Bottom Right View of Binary Tree
Full screen
Console