top view of a binary tree code example
Example 1: gfg top view of tree
class Obj
{
public:
Node *root;
int dis;
Obj(Node *node, int dist)
{
root = node;
dis = dist;
}
};
void topView(Node *root)
{
queue<Obj*> q;
q.push(new Obj(root, 0));
map<int,int> m;
while(!q.empty())
{
Obj *ob = q.front();
q.pop();
if(m.find(ob->dis) == m.end())
m[ob->dis] = ob->root->data;
if(ob->root->left != NULL)
q.push(new Obj(ob->root->left, ob->dis-1));
if(ob->root->right != NULL)
q.push(new Obj(ob->root->right, ob->dis+1));
}
for(auto it=m.begin(); it!=m.end(); it++)
cout << it->second << "\t";
cout << endl;
}
Example 2: top view of binary tree c++
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
class Node {
public:
Node *left, *right;
int data;
Node() { left = right = 0; }
Node(int data)
{
left = right = 0;
this->data = data;
}
};
class Tree {
public:
Node* root;
Tree() { root = 0; }
void topView()
{
queue<pair<Node*, int> > q;
q.push(make_pair(root, 0));
int hd = 0, l = 0, r = 0;
stack<int> left;
vector<int> right;
Node* node;
while (q.size()) {
node = q.front().first;
hd = q.front().second;
if (hd < l) {
left.push(node->data);
l = hd;
}
else if (hd > r) {
right.push_back(node->data);
r = hd;
}
if (node->left) {
q.push(make_pair(node->left, hd - 1));
}
if (node->right) {
q.push(make_pair(node->right, hd + 1));
}
q.pop();
}
while (left.size()) {
cout << left.top() << " ";
left.pop();
}
cout << root->data << " ";
for (auto x : right) {
cout << x << " ";
}
}
};
int main()
{
Tree t;
t.root = new Node(1);
t.root->left = new Node(2);
t.root->right = new Node(3);
t.root->left->right = new Node(4);
t.root->left->right->right = new Node(5);
t.root->left->right->right->right = new Node(6);
t.topView();
cout << endl;
return 0;
}