Home » Technical Interview Questions » Tree Interview Questions » Print Right View of a Binary Tree

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

Print Right View of a Binary Tree

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.

READ  Boundary Traversal of binary tree

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.

READ  Print a Binary Tree in Vertical Order

Space Complexity

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup