Wrong Tree Being Constructed By Input

#1

There are 3 functions in the Tree class which work in my algo. I saw the algo to build tree from Level order from CB Discussion site and implemented it. When I ran it on my custom tree input, wrong tree is being constructed, although on dry run, I think it’s correct. The other 2 functions are working as expected, and they give the correct bottom view corresponding to the constructed tree. Please check why a wrong tree is getting constructed.

here’s the code:

#2

hello @Doctor_Insult
I m not getting ur logic.

pls try to cross verify with this code.

void bottomViewHelper(node *root, int level, int dist, map<int, pair<int, int> > &mp) {
if(root == NULL) {
    return;
}
if(mp.find(dist) == mp.end() or level>=mp[dist].second) {
    mp[dist] = {root->data, level};
}
bottomViewHelper(root->left, level+1, dist-1, mp);
bottomViewHelper(root->right, level+1, dist+1, mp);
}
void bottomView(node *root)
{
   map<int, pair<int, int> >mp;
   bottomViewHelper(root, 0, 0, mp);
   for(auto val:mp){
   cout<<val.second.first<<" ";
   }
}
#3

I used the logic used here to construct the tree

Please see the function build_tree_lvl() and tell why it constructs the wrong tree. I have used inorder and preorder traversals to check the constructed tree and it comes out to be different than what I had intended. No need to check bottom view function, it works correctly. It gives correct bottom view of the tree (wrongly) constructed. Please see my code again.

#4

image

here u r not popping out ur front node from the queue ,that why ur tree is not getting constructed properly.

still ur implementation is complex. the algorithm is simple based on level order technique.
image

1 Like
#5

Thanks a lot for your help. I was stuck at this question for the last 3 days. Thanks a lot!!!