Bottom View of BT Problem

#1

4 out of 5 test cases are showing Run Error.

#include <iostream>
#include <map>
#include <vector>
using namespace std;

class node{
public:
    int data;
    node *left;
    node *right;
    // construct.
    node(int d){
        data = d;
        left = NULL;
        right = NULL;
    }
};


void bottomView(node *root, map<int,int> &m, int l){
    // base case
    if(!root){
        return;
    }

    // rec case
    m[l] = root->data;
    bottomView(root->left,m,l-1);
    bottomView(root->right,m,l+1);

}

// Level Order Build of BT
node *buildTree(vector<int> v, int i){
    if(v[i] == -1){
        return NULL;
    }

    node *root = new node(v[i]);
    root->left = buildTree(v,2*i);
    root->right = buildTree(v,2*i+1);

    return root;
}

int main() {
    vector<int> v;
    v.push_back(-1);
    while(cin){
        int x;
        cin>>x;
        v.push_back(x);
    }
    node *root = buildTree(v,1);

    map<int,int> m;
    int line = 0;
    bottomView(root,m,line);

    for(auto i:m){
		cout<<i.second<<" ";
    }

}
#2

Hi @anuragdeol2017
ur approach is not correct… if u have done the top view question then its very similar to that… refer this --> https://ide.codingblocks.com/s/619391

#3

hey, i have tried modifying the vertical order traversal approach. It’d be really helpful if you could tell why is this approach wrong

#4

hi so basically for bottom view u would have to figure out the base length of tree… but what u are trying to do is simply pushing elements in map according to level… u have to consider both level and horizontal distance… try to dry run my code… u would getter better insight…

#5

for more explanation u can refer this https://www.techiedelight.com/print-bottom-view-of-binary-tree/

#6

can you please provide any test case for which i can dry run my as well as your code, so that i know, where exactly my code is failing and why is yours better

#7

consider this
20 40 60 204 -1 92 65 68 -1 21 -1 -1 85 24 -1 -1 -1 -1 -1 -1 -1
try to dry run on both the codes…

#8

hi… is it clear now??

#9

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.

#10

Hey, i changed my buildTree() function, and now only one test case is giving wrong answer.
But for the test case that you gave, the output is same as your code i.e. 20 40 60 204 -1 92 65 68 -1 21 -1 -1 85 24 -1 -1 -1 -1 -1 -1 -1

Here is my code with new buildTree() func:-

#include <iostream>
#include <map>
#include <queue>
using namespace std;

class node{
public:
int data;
node *left;
node *right;
// construct.
node(int d){
    data = d;
    left = NULL;
    right = NULL;
}
};


void bottomView(node *root, map<int,int> &m, int l){
// base case
if(!root){
    return;
}

// rec case
m[l] = root->data;
bottomView(root->left,m,l-1);
bottomView(root->right,m,l+1);

}

// Level Order Build of BT
node *buildTree(){
int d;
cin>>d;
if(d == -1){
    return NULL;
}

node *root = new node(d);
queue<node *> q;
q.push(root);
while(!q.empty()){
    node *temp = q.front();
    q.pop();
    int lc,rc;
    cin>>lc>>rc;
    if(lc != -1){
        temp->left = new node(lc);
        q.push(temp->left);
    }
    if(rc != -1){
        temp->right = new node(rc);
        q.push(temp->right);
    }
}

return root;

}

void print(node *root){
// base case
if(!root){
    return;
}



// rec case
cout<<root->data<<" ";
print(root->left);
print(root->right);

}

int main() {
node *root = buildTree();

map<int,int> m;
int line = 0;
bottomView(root,m,line);

for(auto i:m){
		// cout<<"Line: "<<i.first<<"-->"<<i.second;
		cout<<i.second<<" ";
}


}
#11

hi anurag
u are not understanding… problem tumhare bottomview function ke sath hai… not buildtree
if u are facing so much difficulty i suggest u to watch any youtube video on same as it seems that u are not able to understand the logic through chat…

#12

yes i get your point. i just wanted to make clear that previously my buildTree() function was wrong and leading to segmentation fault.
Leaving that aside, i dont understand why my code is failing. The test case you gave is successfully running in my code. I request you to check the same.
Can you please give such a test case which fails for my code but not yours. It’ll be helpful to dry run such a test case.

#13

20 8 22 5 3 4 25 -1 -1 10 14 -1 -1 -1 -1 -1 -1 -1 -1
ur code is failing on this test case… try to dry run ur code and mine on the same input…

#14

oh i see. now i understood why my code is failing.

#15

shall i mark it as resolved now?

#16

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.