Scaler
Academy
Data Science
Neovarsity
New
Skill Test
Free Masterclass
Search for Articles, Topics
Print Right View of A Binary Tree

Print Right View of A Binary Tree

By Aman Kumar
7 mins read
Last updated: 15 Sep 2023
238 views
Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Start Learning View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Overview

The right view of binary tree is the set of nodes seen by an observer as standing to the right of a given binary tree. The nodes visible to the observer will be the rightmost nodes at each level. All the other nodes (which will lie to the left of the rightmost nodes) will be hidden since they will lie behind the rightmost nodes in their respective levels.

Takeaways

Time and Space complexity:

  • Time Complexity: O(n)
  • Space Complexity : O(n)

Introduction

Imagine you're a Star Wars character leading a bunch of Resistance spaceships to attack a First Order base called the Death Tree (similar to the Death Star).

You command your troopers to get in a linear formation and attack the base at once. The launched missiles hit the base on the right side at once as shown.

Right View of A Binary Tree in Data Structure

The set of nodes where the explosion is taking place makes up the right view of binary tree. Having gained a visual introduction, let us describe the right view of the binary tree in the upcoming section.

What is the Right View of Binary Tree?

The right view of binary tree is the part of the tree observed by an observer standing right to the tree and facing it.

Therefore, the right view consists of the rightmost nodes of each valid level of the tree.

But, what is a level?

We can define the level of a binary tree as the set of nodes that have an equal number of edges between themselves and the root node (that is, nodes equidistant from the root).

For example, consider the tree with root node as 1: What is the Right View of Binary Tree

The nodes present in each level are given as:

LevelNodes
01
12, 3
26, 7, 5, 4
39, 8

Please note that you can start labelling the levels from either 0 or 1.

Example of Right View of Binary Tree

Consider again the tree we used above. As we said earlier, the rightmost node of each level will be part of our right view of the binary tree. That is:

LevelNodesRightmost Node
011
12, 33
26, 7, 5, 44
39, 88

Therefore, the right view of the binary tree is

Or, visually, the right view of the binary tree is as follows:

Example of Right View of Binary Tree

Taking another example, consider the tree shown below:

Right View of Binary Tree Example

LevelNodesRightmost Node
011
12, 33
25, 44
366
477
588

Therefore, the right view of the given binary tree is

Algorithm

There are two approaches to solve this problem, one is recursive (depth-first-search based) approach, while the other is iterative (breadth-first-search based) approach.

Recursive / DFS Approach

Intuition

  1. DFS is one of the most basic traversal techniques for a graph/tree, therefore, we can try solving our problem using it.
  2. Suppose I am in a given level, it appears that the algorithm should consider the right subtree with higher importance than the left one, since we have to print the rightmost node. This can be achieved by a right-oriented pre-order traversal, that is, current node, followed by right subtree, followed by the left subtree.
  3. In any given level, the algorithm must ONLY print the rightmost node, and if it has been printed, the algorithm must not print any other node (in that level).
  4. It can be achieved by using a variable which keeps track of the last level for which the rightmost node has been printed.
  5. Now, if that variable's value is less than the value of the given level, it means that we are in a level whose rightmost node has not been printed. Therefore, we must print whatever node we first encounter/process in this level.
  6. Since our traversal is right oriented (see point 2), then we will always reach the rightmost node of a level before other nodes of that level.

Now, let's see the algorithm where we used all the points we discussed above.

The Recursive Algorithm

  1. Initialize two variables:

    a. curr_level: The current level of the tree we are currently present in during the traversal

    b. last_printed_level: The last level for which the rightmost node has been printed/stored.

  2. Process the following sequentially in a recursive manner:

    a. Current node

    b. Right subtree

    c. Left subtree

  3. At the current node (if it is not null) check whether the current level > last printed level.

    a. If Yes: Print / store the current node and update the value of last_printed_level to curr_level.

    b. If No: Continue

  4. Before calling the function recursively on the right and left subtree, increase the value of level by 1.

Note:

The variable last_printed_level should either be a global variable (not recommended) or be passed by reference to function calls (recommended). This is done to ensure that the current level is compared to most recently updated value of last_printed_level.

Please see the animated gif below to for a better visual understanding of the algorithm. the recursive algorithm

Iterative / BFS Approach

Intuition

This, perhaps, is the most intuitive way of solving this problem.

  1. We travel the entire tree level by level (from right to left).
  2. At each level, we print/store the right most node.
  3. After the algorithm is done processing the entire tree, we will obtain the right view of the binary tree given to us.

The Iterative Algorithm

  1. Initialize a queue data structure ((commonly used in BFS algorithm) with the root node and a LevelEnd character to mark a level's end in the queue. Commonly, nullptr or NULL is used as LevelEnd in C/C++, while None is used in Python.

  2. While the queue is not empty, do the following:

    a. Pop the front of the queue, and call it frontVal

    b. If frontVal is LevelEnd, and the resultant queue is not empty, pop and print the front value of the resultant queue (this is the rightmost node of the given level), and also push a LevelEnd character into the queue.

    c. If frontVal is LevelEnd and the resultant queue is empty, break out of the while loop.

    d. If frontVal is not LevelEnd, then push its right child followed by left child into the queue (they must exist, of course).

Explanation

  1. The above stated algorithm is just a right-oriented version of the standard Level-Order-Traversal algorithm.
  2. Between any two LevelEnd characters, an entire level of the given tree is present (except, of course, the level 0, that is, the root node)
  3. Since we give priority to the right child node over the left child node while pushing into the queue (see step 2.c of the algorithm) we ensure that the queue contains levels in a right to left fashion with respect to the binary tree given.
  4. Because of the above point, we can be sure that the node just after the LevelEnd character in the queue is the rightmost node in the given binary tree's level. Therefore, we printed it in step (2.b) of the algorithm.

Note:

Please note that it is not necessary to push the right child first. If we had pushed the left child of the current node into the queue, then in step (2.b) we would print the node just before the LevelEnd characters instead of other way round.

The reason for this is that the resultant queue will contain levels in left to right fashion with respect to the given binary tree.

See the animated gif given below for a better visual understanding of the algorithm.

the iterative algorithm

Right View Of Binary Tree: Code Implementation

Before you see the code solution below, it is recommended that you try to implement the above-discussed algorithms yourself here on InterviewBit.

C++ (DFS Approach)

Explanation

  • As explained in the algorithm, the code traverses the given tree in the fashion (current node-> right subtree->left subtree).

  • At each node, if the last_printed_level<curr_level, we print the current level.

  • To keep the value of the variable last_printed_level up-to-date, we pass it by reference to each recursive call.

Python (DFS Approach)

C++ (BFS Approach)

Explanation

  • A queue is initialized which can store node pointer values.
  • We perform a right-oriented level-order traversal. Therefore, after popping out a LevelEnd character, the next value in queue is the rightmost node of the level we are currently processing in the queue. So, we print it and pop it from the queue.
  • Rest all the nodes are not printed.

Python (BFS Approach)

Complexity Analysis

  1. Time Complexity: Since all the nodes are processed exactly once, therefore if the number of nodes present in the tree is of order nn, then the time complexity of both the algorithms we used to find the right view of the binary tree is:
O(n)\mathcal{O}(n)
  1. Space Complexity: a. DFS Solution : O(h)\mathcal{O}(h), where hh is the height of the binary tree b. BFS Solution : O(n)\mathcal{O}(n), where nn is the order of number of nodes in the binary tree

Conclusion

  1. Right view of binary tree consists of the rightmost nodes of each level in the binary tree.
  2. Two methods can be used to obtain the right view of binary tree; one uses a DFS approach, and the other uses a BFS approach.
  3. While using the DFS (recursive) approach, we keep track of the level we are currently in, and the last level for which we have already obtained the rightmost node.
  4. While using the BFS (iterative) approach, we perform a level order traversal and store/print the rightmost node in any given level.