Print Right View of a Binary Tree

Problem: Given a Binary Tree, print right view of it. Right view of a Binary Tree is set of nodes visible when tree is visited from right side.

For example: Given the following tree, the right view of tree is 30, 40, 45, 12

Method 1: The naive approach is to do level order traversal of the binary tree and print the last node of all the levels.

Method 2: We can also do this problem using recursion. The idea is to keep track of maximum level and the current level. Here we traverse the tree in a manner that right sub tree is visited before left sub tree. Whenever current level is greater than the maximum level so far obtained, we print the current node because this is the last node in its level.

Below is the implementation of the idea.

#include <bits/stdc++.h>
using namespace std;
 
struct node
{
    int data;
    node *left;
    node *right;
};
 
/* utility funcion for new node in binary tree */
node* newNode(int data)
{
    node *temp = new node();
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
/* function to print the right view */
void rightView(node *root, int *max_level, int cur_level)
{
    /* base case */
    if(root == NULL)
        return;
 
    /* if the current node is last node in level */
    if(*max_level < cur_level)
    {
        cout<<root->data<<" ";
        *max_level = cur_level;
    }
 
    /* recursive call for left sub tree and right sub tree */
    rightView(root->right, max_level, cur_level + 1);
    rightView(root->left, max_level, cur_level + 1);
}
 
/* driver function */
int main()
{
    node *root              = newNode(30);
    root->left              = newNode(20);
    root->right             = newNode(40);
    root->left->left        = newNode(10);
    root->right->left       = newNode(37);
    root->right->right      = newNode(45);
    root->left->left->right = newNode(12);
 
    int max_level = 0;
    rightView(root, &max_level, 1);
    cout<<"\n";
 
    return 0;
}

Output:

30 40 45 12

Time Complexity: O(n)