Right View of Binary Tree in Java

In this article we look into another problem related to binary trees. Given a binary tree we have to print the Right View. We will discuss the approaches to solve this problem with their implementations and code. Along with this we will also look into the time and space complexities of our approaches.

By right view of binary tree we mean the nodes visible to us when the tree is viewed from the right side. In other words, the nodes which are present at the last of each level, the root being the first level.

Let us consider this binary tree:

The Right View of this binary tree will give output: 1 3 6 7.

The nodes present in right view are marked in the figure. We start from the root node 1 at level 1 then we go down each level printing the last node present at each level. At level 2 node 3 is the last node so print it, at level 3 node 6 and at the last level 4 node 7 is the only node.

Note: If a level contains only one node then that node is a part of our Right View.

Approach 1 (Recursive Approach)

We traverse the tree in a way that we keep track of current level by passing a max_level variable by reference to each recursive call or maintain a static variable so to keep track of the maximum level reached. When we process the current node we check if it’s level is more than max level till now. If current node’s level is greater than max_level we print it and update max level with current node’s level. Otherwise, we traverse for the Right Subtrees at first then the Left subtrees. Traversing Right subtrees first help us print the last node of each level.

Below is the implementation of above in Java:

Output:

Time Complexity: We do a traversal of all nodes in tree so the complexity is O (n).

Space Complexity: We call the function rightViewHelper() for each node so if System stack space is considered the complexity is O (n).

Approach 2 (Iterative Approach Using Queue)

We use Level Order Traversal technique. We print the Right-most node at each level. At first, we are going to enqueue root node in a Queue of type Node. After this we enqueue left child and right child of the current node. The order of insertion of child node does not matter here. While processing each node if it is the last node at that level we print it.

Output:

Time Complexity: We do Level by Level traversal of all nodes so the complexity is O (n) where n is the number of nodes in a Binary tree.

Space Complexity:The Queue we use will at most store the nodes present at all levels and if we are given a skewed binary tree then it will store nodes at all levels so worst case complexity is O(n).

That’s it for the article you can try and execute the program in your local IDE or Java online compiler to see the output.

Comment down below to ask your doubts if any.

1 thought on “Right View of Binary Tree in Java”

Leave a Comment

Your email address will not be published.