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