Given a binary tree, print the top-Right view of it. The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. The output nodes should be printed from left to right.
In the Top-Right view, on viewing the tree at an angle of 45 degrees from the Top-Right side and only a few nodes would be visible and rest would be hidden behind them.
Examples :
Input :
1
/ \
2 3
/ / \
4 5 7
Output : Top-Right view: 1 3 7
Input :
1
/ \
2 3
\
4
\
5
\
6
Output : Top-Right view: 1 3 5 6
Approach :
- The problem can be solved using Vertical Order Traversal.
- Keep track of the horizontal distance and level of a node. Consider the level of a tree at an angle of 45 degrees (as explained in an example), so whenever we move towards the Right, its level would increase by one and horizontal distance is also increased by one.
- A Map is used to map the horizontal distance of the node with the node’s Data and vertical distance of the node.
- A node whose level is more than maximum level and horizontal distance so far, Print the node because this is the last node in its level
Implementation :
// C++ Program to print Top-Right View of Binary Tree
// using hashmap and recursion
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node {
// Data of the node
int data;
// Horizontal Distance of the node
int hd;
// Reference to left node
struct Node* left;
// Reference to right node
struct Node* right;
};
// Initialising node
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->hd = INT_MAX;
node->left = NULL;
node->right = NULL;
return node;
}
void printTopRightViewUtil(Node* root, int height,
int hd, map<int, pair<int, int> >& m)
{
// Base Case
if (root == NULL)
return;
// If the node for particular horizontal distance
// is not present in the map, add it.
// For top view, we consider the first element
// at horizontal distance in level order traversal
if (m.find(hd) == m.end()) {
m[hd] = make_pair(root->data, height);
}
else{
pair<int, int> p = (m.find(hd))->second;
if (p.second > height) {
m.erase(hd);
m[hd] = make_pair(root->data, height);
}
}
// Recur for left and right subtree
printTopRightViewUtil(root->left, height + 1, hd, m);
printTopRightViewUtil(root->right, height + 1, hd+1, m);
}
void printTopRightView(Node* root)
{
// Map to store horizontal distance,
// height and node's data
map<int, pair<int, int> > m;
printTopRightViewUtil(root, 0, 0, m);
// Print the node's value stored by printTopRightViewUtil()
for (map<int, pair<int, int> >::iterator it = m.begin();
it != m.end(); it++) {
pair<int, int> p = it->second;
cout << p.first << " ";
}
}
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->left->right->right = newNode(5);
root->left->right->right->right = newNode(6);
cout << "Top-Right View : ";
printTopRightView(root);
return 0;
}
Output :
Top-Right View : 1 3 5 6