Right View Of A Binary Tree



Program for finding the right view of a binary tree

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

using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
    Node() : data(0), left(nullptr), right(nullptr) {}
    Node(int x) : data(x), left(nullptr), right(nullptr) {}
    Node(int x, Node *left, Node *right) : data(x), left(left), right(right) {}
};

void RightView (Node * root) {

    if (root == nullptr)
       return;
    
    vector<int> right_view;
    
    queue<Node*> pq; // Parent Queue
    queue<Node*> cq; // Child Queue
    
    pq.push(root);
    
    while (!pq.empty() or !cq.empty()) {
        
        // Store the right most node at every level in the right view vector
        if (!pq.empty()) 
            right_view.push_back(pq.back()->data);
        
        while (!pq.empty()) {
            Node * node = pq.front();
            pq.pop();
            if (node->left) {
                cq.push(node->left);
            }
            if (node->right) {
                cq.push(node->right);
            }
        }
        
        // Store the right most node at every level in the right view vector
        if (!cq.empty()) 
            right_view.push_back(cq.back()->data);
        
        while (!cq.empty()) {
            Node * node = cq.front();
            cq.pop();
            if (node->left) {
                pq.push(node->left);
            }
            if (node->right) {
                pq.push(node->right);
            }
        }
    }
    cout << "Right View : ";
    for (const auto& node : right_view)
        cout << node << " ";
}

int main() {

/* Constructed binary tree is
               9 <----
             /   \
            5     16 <----
          /  \   
         3   7  <----
            / \       
           6   8  <----
*/
    Node node_6 (6, nullptr, nullptr);
    Node node_8 (8, nullptr, nullptr);
    Node node_3 (3, nullptr, nullptr);
    Node node_7 (7, &node_6, &node_8);
    Node node_5 (5, &node_3, &node_7);
    Node node_16 (16, nullptr, nullptr);
    Node root (9, &node_5, &node_16);

    RightView (&root);

    return 0;
}

Output

Right View : 9 16 7 8



Copyright (c) 2019-2024, Algotree.org.
All rights reserved.