Print Bottom-Right View of a Binary Tree
In this article, we will address the problem of printing the bottom-right view of a binary tree. The task is to find and print the rightmost elements at each level of the binary tree when viewed from the bottom. To accomplish this, we will employ a depth-first search (DFS) approach to traverse the tree and maintain a record of the rightmost elements at each level.

Problem Statement
Given a binary tree, we aim to print the bottom-right view of the tree. The bottom-right view of a binary tree is the collection of nodes visible when the tree is viewed from the right side at each level. In other words, for each level of the tree, we want to print the rightmost node at that level.
Example
Let's consider a binary tree as an example:
10
/ \
2 4
/ / \
3 6 5
\
7
/ \
8 11
The bottom-right view of this tree is [5, 11, 8]
when viewed from the right side at each level, as
indicated by the arrows in the tree diagram.
Idea to Solve the Problem
To print the bottom-right view of the binary tree, we can perform a depth-first traversal of the tree while
maintaining a record of the rightmost node at each level. We will use a HashMap
to store this
information, where the key represents the level of the node, and the value is the rightmost node's value at that
level. We'll start the traversal from the root node with a distance of 0 and increment the distance when moving to
the left child and stay at the same distance when moving to the right child.
Pseudocode
Here is the pseudocode for solving the problem:
function bottomRightView(node, distance, record):
if node is not null:
record.put(distance, node.data)
bottomRightView(node.left, distance + 1, record)
bottomRightView(node.right, distance, record)
function printBottomRight():
record = empty HashMap
bottomRightView(root, 0, record)
distance = 0
while distance < size of record:
print record.get(distance)
increment distance by 1
Algorithm Explanation
- Initialize an empty
HashMap
calledrecord
to store the rightmost nodes at each level. - Call the
bottomRightView
function starting from the root node with an initial distance of 0. - In the
bottomRightView
function:- If the current node is not null, add the node's data to the
record
at the current distance. - Recursively call the function for the left child with an increased distance (moving left).
- Recursively call the function for the right child without changing the distance (moving right).
- If the current node is not null, add the node's data to the
- After the traversal is complete, iterate through the
record
map, starting from distance 0, and print the rightmost node's value at each level. - Increment the distance by 1 in each iteration until all the rightmost nodes at each level are printed.
Code Solution
-
1) Bottom right view of binary tree in java
2) Bottom right view of binary tree in c++
3) Bottom right view of binary tree in c#
4) Bottom right view of binary tree in vb.net
5) Bottom right view of binary tree in php
6) Bottom right view of binary tree in node js
7) Bottom right view of binary tree in python
8) Bottom right view of binary tree in ruby
9) Bottom right view of binary tree in scala
10) Bottom right view of binary tree in swift
11) Bottom right view of binary tree in kotlin
12) Bottom right view of binary tree in golang
Time Complexity of the Code
The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we
visit each node once during the depth-first traversal, and the HashMap
operations take constant time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment