Q:

# Right View of Binary Tree

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```

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```