Print Right View of a Binary Tree

Problem Statement

The problem “Print Right View of a Binary Tree” states that you are given a binary tree. Now you need to find the right view of this tree. Here, right view of the binary tree means to print the sequence as the tree looks when looked from the right direction.

Example

2 7 4 6

Explanation

If you observe the binary tree in the right direction. We are able to see only the nodes which are printed in the output. Because the nodes 3 and 5 get hidden behind 7 and 4 respectively.

Approach to print right view of a binary tree

In this problem, we need to find the right view of the binary tree. The problem can be solved using two approaches. One of them uses a queue and the other one uses recursion. First, we will discuss the approach using the queue. So, to solve the problem using a queue. We start from the root of the binary tree. For each level of the tree, we keep on storing the nodes in the queue. For storing the nodes of the next level, we do have to traverse over the nodes of the current level. So when we are traversing over the nodes of the current level. We print the last node at this level. When we observe the tree from the right side. The only node which is visible to us is the rightmost node at a level. This approach uses a queue that takes space.

Let’s discuss the solution using recursion. The solution is very similar to that of finding the left view of the tree. In this approach. We simply do a traversal of the tree which is opposite to that of inorder traversal. But we also track the level we are currently at and the maximum level attained until now. As we move to the right subtree before the left subtree. Whenever we enter the new level in the tree. We first encounter the rightmost node. So we always keep a check if the current level is greater than the maximum level, we print the node. The approach is better if we don’t consider the space required for the compiler stack. The space complexity for the problem is dependent on the height of the tree if we do consider the space taken by the compiler stack.

Code

C++ code to Print Right View of a Binary Tree

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

int main(){
  node *root = create(2);
  root->left = create(3);
  root->right = create(7);
  root->left->left = create(5);
  root->left->right =create(4);
  root->left->right->left = create(6);

  int max_level = 0;
  printRightView(root, 1, max_level);
}

2 7 4 6

Java code to Print Right View of a Binary Tree

import java.util.*;

class node{
  int data;
  node left;
  node right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  public static void main(String[] args){
    node root = create(2);
    root.left = create(3);
    root.right = create(7);
    root.left.left = create(5);
    root.left.right =create(4);
    root.left.right.left = create(6);
    
    max_level = 0;
    printRightView(root, 1);
  }
}

2 7 4 6

Complexity Analysis

Time Complexity

O(N), we are just traversing over the nodes in the tree. So if there are N nodes in the tree, the algorithm requires O(N) operations to perform.

Space Complexity

O(1). If space used by compiler stack is not considered, else O(H) space is required.