Right View of a Binary Tree

You are given a Binary Tree, you need to print the right view of the tree.

Consider the tree in the below figure.

The right view of the tree would be { 8, 10, 14, 13 }.

Algorithm:

  1. Create a queue which would store the Nodes of the trees. Insert the root node in the tree.
  2. while the queue is not empty, do the following –
    You need to print the last node of each level in the tree. To do so, at each iteration, find out the size of the queue. Iterate for i = 1 to N where N is the size of the current level. In each iteration, pop a node from the queue. If the node is the last node in the level, print the value. Push the left and right child of the current node to the queue and move to the next node.

Check out the complete code in C++.

#include <bits/stdc++.h>

using namespace std;

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

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void rightView(Node* root){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        for(int i = 1; i <= n; i++){
            Node* temp = q.front();
            q.pop();
            if(i==n){
                cout<<temp->data<<" ";
            }
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
    }
}


void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    cout<<"Level Order traversal => ";
    levelOrderTraversal();
    cout<<endl;
    cout<<"Right View => ";
    rightView(root);
    return 0;
}

Also, check out another popular interview problem Majority Element.

One comment

Leave a Reply

Your email address will not be published.