-
Notifications
You must be signed in to change notification settings - Fork 253
/
Print vertical order of tree.cpp
81 lines (72 loc) · 1.16 KB
/
Print vertical order of tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<queue>
#include<math.h>
#include<map>
#include<vector>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int d)
{
data = d;
left = NULL;
right = NULL;
}
};
node* buildtreeLevel()
{
queue<node*>q;
int d;
cin >> d;
node* root = new node(d);
q.push(root);
int c1, c2;
while (!q.empty())
{
node* f = q.front();
q.pop();
cin >> c1 >> c2;
if (c1 != -1)
{
f->left = new node(c1);
q.push(f->left);
}
if (c2 != -1)
{
f->right = new node(c2);
q.push(f->right);
}
}
return root;
}
//pass map by reference
void vertical_order_print(node*root,int d, map<int,vector<int>> &m){
//base case
if(root==NULL){
return;
}
//otherwise
m[d].push_back(root->data);
vertical_order_print(root->left,d-1,m);
vertical_order_print(root->right,d+1,m);
return;
}
int main()
{
int N;
cin>>N;
node* root = buildtreeLevel();
map<int,vector<int>>m;
int d=0;
vertical_order_print(root,d,m);
for(auto p:m){
//cout<<p.first<<"->";
for(int x:p.second){
cout<<x<<",";
}
cout<<endl;
}
}