Last Updated: 8 Jan, 2021

Bottom Right View of Binary Tree

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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.

Solve now