top view of binary tree c 2b 2b

1/* This is not the entire code. It's just the function which implements 
2   bottom view. You need to write required code. */
3
4// Obj class is used to store node with it's distance from parent.
5class Obj
6{
7    public:
8        Node *root;
9        int dis; // distance from parent node. distance of root node will be 0.
10
11        Obj(Node *node, int dist)
12        {
13            root = node;
14            dis = dist;
15        }
16};
17
18void topView(Node *root)
19{
20    queue<Obj*> q;
21    q.push(new Obj(root, 0));
22    map<int,int> m;
23
24    while(!q.empty())
25    {
26        Obj *ob = q.front();
27        q.pop();
28		
29      	/* insert node of unique distance from parent node. ignore repitation 
30           of distance. */
31        if(m.find(ob->dis) == m.end())
32            m[ob->dis] = ob->root->data;
33
34        if(ob->root->left != NULL)
35            q.push(new Obj(ob->root->left, ob->dis-1)); 
36        if(ob->root->right != NULL)
37            q.push(new Obj(ob->root->right, ob->dis+1));
38    }
39
40  	// printing nodes.
41    for(auto it=m.begin(); it!=m.end(); it++)
42        cout << it->second << "\t";
43
44    cout << endl;
45}

1// C++ Program to print Top View of a binary Tree
2
3#include <iostream>
4#include <queue>
5#include <stack>
6using namespace std;
7
8// class for Tree node
9class Node {
10public:
11	Node *left, *right;
12	int data;
13	Node() { left = right = 0; }
14	Node(int data)
15	{
16		left = right = 0;
17		this->data = data;
18	}
19};
20
21/*
22		1
23		/ \
24		2 3
25		\
26		4
27		\
28			5
29			\
30			6
31	Top view of the above binary tree is
32	2 1 3 6
33*/
34
35// class for Tree
36class Tree {
37public:
38	Node* root;
39	Tree() { root = 0; }
40
41	void topView()
42	{
43		// queue for holding nodes and their horizontal
44		// distance from the root node
45		queue<pair<Node*, int> > q;
46
47		// pushing root node with distance 0
48		q.push(make_pair(root, 0));
49
50		// hd is currect node's horizontal distance from
51		// root node l is currect left min horizontal
52		// distance (or max in magnitude) so far from the
53		// root node r is currect right max horizontal
54		// distance so far from the root node
55
56		int hd = 0, l = 0, r = 0;
57
58		// stack is for holding left node's data because
59		// they will appear in reverse order that is why
60		// using stack
61		stack<int> left;
62
63		// vector is for holding right node's data
64		vector<int> right;
65
66		Node* node;
67
68		while (q.size()) {
69
70			node = q.front().first;
71			hd = q.front().second;
72
73			if (hd < l) {
74				left.push(node->data);
75				l = hd;
76			}
77			else if (hd > r) {
78				right.push_back(node->data);
79				r = hd;
80			}
81
82			if (node->left) {
83				q.push(make_pair(node->left, hd - 1));
84			}
85			if (node->right) {
86				q.push(make_pair(node->right, hd + 1));
87			}
88
89			q.pop();
90		}
91		// printing the left node's data in reverse order
92		while (left.size()) {
93			cout << left.top() << " ";
94			left.pop();
95		}
96
97		// then printing the root node's data
98		cout << root->data << " ";
99
100		// finally printing the right node's data
101		for (auto x : right) {
102			cout << x << " ";
103		}
104	}
105};
106
107// Driver code
108int main()
109{
110	// Tree object
111	Tree t;
112	t.root = new Node(1);
113	t.root->left = new Node(2);
114	t.root->right = new Node(3);
115	t.root->left->right = new Node(4);
116	t.root->left->right->right = new Node(5);
117	t.root->left->right->right->right = new Node(6);
118	t.topView();
119	cout << endl;
120	return 0;
121}
122