Home » Interview coding problems/challenges

Right View of Binary Tree

In this article, we are going to see how to find the right view of a binary tree? This problem has been featured in interview coding round of Snapdeal, Amazon, MakeMyTrip, Adobe etc. Submitted by Radib Kar, on February 09, 2019

Problem statement

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.

Example

    For the above tree:
    
    Output: Right view
    2, 5, 9, 4

Solution

Right view of a binary tree

Right view of a binary tree means the nodes which are visible when tree is view from right direction only.

The above problem can be solved using level order traversal. For every level traversed, print only the rightmost node.

Algorithm

Pre-requisite:

A Queue, input binary tree

FUNCTION rightView(root)
1.  Declare a queue q to store tree nodes.
    EnQueue (q, root);
    EnQueue (q, NULL);
    NULL is EnQueued after end of each level. Root determines level-0  
    While (q is not empty)
        temp=DeQueue(q)
        IF (temp==NULL)
            IF (q is not empty)
                EnQueue (q, NULL);				
            END IF
            Printstore  //it actually contains the right most node 
                        //of the last level traversed				
        ELSE			
            store=temp->data //update store to current temp->data every time 
        END IF
        
        IF (temp->left is not NULL)
            EnQueue (q, temp->left);
        IF (temp->right is not NULL)
            EnQueue (q, temp->right);
        END IF-ELSE
    END WHILE
END FUNCTION

C++ Implementation

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

// tree node is defined
class TreeNode{    
	public:
	int data;
	TreeNode *left;
	TreeNode *right;
};

// creating new node for tree
TreeNode* newnode(int data)  
{ 
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return(node); 
} 

void rightView(TreeNode *root)
{
	queue<TreeNode*> q;
	TreeNode* temp;
	int store; //to store the nodes
	
	q.push(root);
	q.push(NULL);

	while(!q.empty()){
		temp=q.front();
		q.pop();
		if(temp==NULL){
			if(!q.empty()){
				q.push(NULL);
			}
			cout<<store<<" "; //printing the rightmost node
		}
		else{
			store=temp->data;
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	} 
}

int main() { 
	//**same tree is builted as shown in example**
	cout<<"same tree is built as shown in example\n";
	
	TreeNode *root=newnode(2); 
	
	root->left= newnode(7); 
	root->right= newnode(5); 
	root->right->right=newnode(9);
	root->right->right->left=newnode(4);
	root->left->left=newnode(2); 
	root->left->right=newnode(6);
	root->left->right->left=newnode(5);
	root->left->right->right=newnode(11);

	cout<<"Right view of the tree is:\n";
	rightView(root);

	return 0; 
} 

Output

same tree is built as shown in example
Right view of the tree is:
2 5 9 4 

Example with explanation

For our example tree...

Root=2;
EnQueue(root)
Queue status: 2
EnQueue(NULL)
Queue status: 2, NULL
----------------------------------------------------

1st iteration
Queue not empty
Queue front is 2
Pop 2
Store=2
Push: 2->left(7) & 2->right(5)
Queue status: NULL, 7, 5
K=3
----------------------------------------------------

2nd iteration
Queue not empty
Queue front is NULL
Pop NULL
Print store, 2
Push: NULL
Queue status: 7, 5, NULL
----------------------------------------------------

3rd iteration
Queue not empty
Queue front is 7
Pop 7
Store=7
Push: 7->left (2) and 7->right (6) only
Queue status: 5, NULL, 2, 6 
----------------------------------------------------

4th iteration
Queue not empty
Queue front is 5
Pop 5
Store=5
Push: 5->right (9) (5->left is NULL)
Queue status: NULL, 2, 6, 9 
----------------------------------------------------

5th iteration
Queue not empty
Queue front is NULL
Pop NULL
Print store, 5
Push: NULL
Queue status: 2, 6, 9, NULL
----------------------------------------------------

6th iteration
Queue not empty
Queue front is 2
Pop 2
Store=2
Push: Nothing (2->left is NULL, 2->right is NULL)
Queue status: 6, 9, NULL 
----------------------------------------------------

7th iteration
Queue not empty
Queue front is 6
Pop 6
Store=6
Push: 6->left (5) & 6->right (11)
Queue status: 9, NULL, 5, 11 
----------------------------------------------------

8th iteration
Queue not empty
Queue front is 9
Pop 9
Store=9
Push: 9->left (4) (9->right is NULL)
Queue status: NULL, 5, 11, 4 
----------------------------------------------------

9th iteration
Queue not empty
Queue front is NULL
Pop NULL
Print store, 9
Push: NULL
Queue status: 5, 11, 4, NULL
----------------------------------------------------

10th iteration
Queue not empty
Queue front is 5
Pop 5
Store=5
Push: Nothing (9->left NULL, 9->right is NULL)
Queue status: 11, 4, NULL 
----------------------------------------------------

11th iteration
Queue not empty
Queue front is 11
Pop 11
Store=11
Push: Nothing (11->left NULL, 11->right is NULL)
Queue status: 4, NULL 
----------------------------------------------------

12th iteration
Queue not empty
Queue front is 4
Pop 4
Store=4
Push: Nothing (11->left NULL, 11->right is NULL)
Queue status: NULL 
----------------------------------------------------

13th iteration
Queue not empty
Queue front is NULL
Pop NULL
Print Store, 4
Now Queue is empty
Push: Nothing (11->left NULL, 11->right is NULL)
Queue status: empty Queue

Exit from program

Hence right view is:
2 5 9 4