Binary tree right side view

We have already read about what the binary tree’s left and top view looks like. So, in this blog, we will print a binary tree right side view.

Let’s move to this blog, 

About binary tree right side view:

We can say all the right nodes at each level that are in the right sub-tree of the binary tree come in the right side view. 

So, we can say that the right side view of a binary tree has that list of all the nodes that are visible when we see the binary tree from the top of the tree from the right side.

How to print the right side view of a binary tree?

To get the binary tree right side view, we have to perform a level-order traversal which is a breadth-first traversal algorithm. Also, to keep track of all the rightmost nodes at each level and to print all the nodes, we have to traverse the binary tree level by level.

So, here is the algorithm:

1. First, we will create an empty list to store all the nodes that are on the right side of the binary tree.
2. Next, we will perform a level-order traversal of the binary tree. And for that, we have to use a queue data structure to keep track of all the nodes.
3. Then, at each level, we will keep track of the rightmost node by traversing the binary tree from to left at each level of the tree. 
4. Finally, add the right node of each level to the result list and print that result as the output.

Right side view of a binary tree code:

Code:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    // Constructor
    Node(int val) {
        data = val;
        left = NULL;
        right = NULL; 
    }
};

vector<int> rightSideView(Node* root) { 
    vector<int> result;

    if (!root) {
        return result;
    }

    queue<Node*> q; 
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();

        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front(); 
            q.pop();

            // Keep track of the rightmost node in the current level
            if (i == levelSize - 1) {
                result.push_back(node->data); 
            }

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return result;
}

int main() {
    // Create a binary tree
    Node* root = new Node(1); 
    root->left = new Node(2); 
    root->right = new Node(3); 
    root->left->left = new Node(4); 
    root->left->right = new Node(5); 
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->right->right = new Node(8); 

    // Output the right side view of the binary tree
    vector<int> rightView = rightSideView(root);
    for (int val : rightView) {
        cout << val << " ";
    }

    return 0;
}

Explanation of the above code:

1. Initially, we will include all the necessary C++ libraries.
2. Then, we create a structure called “Node” to represent each node in the binary tree. So, it will contain three members that are:
   a) data, to store an integer to represent the value of the node.
   b) Node* left, which is a pointer to the left child node of the current node.
   c) Node* right, which is a pointer to the right child node of the current node.
   It also has a constructor that takes an integer value as a parameter and initializes the “left” and “right” pointers to the value “NULL”.
3. Next, we create the “rightSideView” function that takes the TreeNode pointer parameter as the root.
4. This function will return the “vector” as a result variable that contains all the right-side views of the binary tree.
5. The function will checks if the “root” is equal to “NULL” or not. If the tree is empty, then it will return an empty “result” vector.
6. After this, we will make a queue of TreeNode pointer named q. This varaible will perform BFS traversal. So, the root node is pushed into the queue to start the traversal.
7. Now, we will make a “while” loop that continues until the queue “q” is empty. The loop will perform BFS traversal level by level.
   Here, the variable “levelSize” is assigned with the size of the current level which is the number of nodes in the queue at the just start of the levels.
8. Inside the while loop, we make a for loop that runs till “levelSize” variable value to process each node at the current level.
9. Now, the code checks if the current node is the rightmost node of the current level or not. So,
   a) First, we will check if var i is equal to “levelSize – 1” or not, if it is that means this is the rightmost node at the current level.
   b) Then, the value of the rightmost node is then added to the “result” vector using “result.push_back(node->val)”.
10. Inside the “for” loop, the code checks if the current node has a left child or not. If yes, then, it adds the left child to the queue “q”.
    Similarly, the code checks if the current node has the right child. If yes, it adds the right child to the queue “q”.
11. While doing this, it will ensure that all the next level of nodes will be processed in the next iteration.
12. Finally, after traversing the entire binary tree using BFS, the function will return the “result” vector containing the right-side view of the binary tree.

In the above code, the right-side view elements for the given binary tree are [1, 3, 7, 8].