Hello guys, Recently i came across a question in Hackerrank about printing top view of a binary tree. I have solved it using the following approach from GeeksforGeeks:
// function to fill the map
void fillMap(Node *root, int d, int l, map<int,pair<int,int>> &mp){
if(root == NULL)
return;
if(mp.count(d) == 0)
{
mp[d] = make_pair(l,root->data);
}
else{
if(mp[d].first>l)
mp[d] = make_pair(l,root->data);
cout<<"mp[d].first is: "<<mp[d].first<<" is greater than l: "<<l;
}
cout<<endl;
fillMap(root->left,d-1,l+1,mp);
fillMap(root->right,d+1,l+1,mp);
}
// function should print the topView of
// the binary tree
void topView(struct Node *root){
map<int,pair<int,int>> mp;
fillMap(root,0,0,mp);
for(auto m: mp)
cout<<m.second.second<<" ";
}
My output is correct for the following sample:
1
\
2
\
5
/ \
3 6
\
4
O/P : 1 2 5 6
Now my question is:
> if(mp[d].first>l)
> mp[d] = make_pair(l,root->data);
> cout<<"mp[d].first is: "<<mp[d].first<<" is greater than "<<l;
In the following lines, i’m doing mp[d].first>l
which means i’m comparing present level with previous level and updating. So shouldn’t it be mp[d].first<l
? because i always take the top most level.
And when i try to print the values in o/p, this is what i get?
- mp[d].first is: 1 is greater than l: 3
- mp[d].first is: 2 is greater than l: 4
How come 1 is greater than 3 executed?
And also if i print it before doing the operation, nothing is getting printed. Like this:
if(mp[d].first>l)
cout<<"mp[d].first is: "<<mp[d].first<<" is greater than l: "<<l;
mp[d] = make_pair(l,root->data);
why doesn’t it print anything?
I know i’m missing some basic easy concept. But i’m new to maps and pairs. So please help.
Thank You!
Peace!