Tree bottom view

#1


one test case failing

#2

Please see this doubt
i have replied to this recently

if you have more doubts you can ask here

if doubt is resolved please mark it as resolved and also hit a like :grinning:

#3 
              20
            /    \
          8       22
        /   \        \
      5      3       25
            /   \      
          10    14

for this tree it gives correct output, in my code for same horizontal distance it takes later one
but one test case failing
where is problem in my code ?

#4

correct output for this tree is
5 10 3 14 25

but your code is giving
14 25 5 8 3 22
which is wrong

#5

my output is 5 10 3 22 25 , this is wrong, instead it should be 5 10 3 14 25, i think i am doing preorder traversal, so 22 comes later, it is taking 22 overwriting the 14, but i think i should do level order traversal and for same horizontal distance, i should take the later one
right ?

#6

just make one more level
and store level and data two things in hashmap

use this

void helper(node*rt,map<int,pair<int,int>>&hashmap,int level,int hd){
	if(rt==NULL)return;
	if(hashmap.find(hd)==hashmap.end())
		hashmap.insert({hd,{rt->data,level}});
	else{
		pair<int ,int >p=hashmap[hd];
		if(level>=p.second){
			hashmap[hd]={rt->data,level};
		}
		
	}
	helper(rt->left,hashmap,level+1,hd-1);
	helper(rt->right,hashmap,level+1,hd+1);
}
void TreeBottomView(node*rt){
	map<int,pair<int,int>>hashmap;
	helper(rt,hashmap,0,0);
	for(auto it:hashmap){
		cout<<it.second.first<<" ";
	}
	cout<<endl;

}
1 Like
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

@asaurabh_26 Thank you got it