Vertical order traversal

#1

question–>
https://practice.geeksforgeeks.org/problems/print-a-binary-tree-in-vertical-order/1#
code–>


not passing all test cases help

#2

@mr.encoder are u there?

#3

Yes i figured out what side case it is failing but don’t know how to solve it.
image
See this picture
Your code will print:
2
1 5 3
4
But what it will actually need is:
2
1 3 5
4

#4

okay i think if we do bfs (level order traversal ) it is pass right,i will try

#5

Yes try to do it, after doing that share your updated code if it passes test cases. Gfg is making their test cases too tight. Don’t know why

#6

How did you got to know that i am taking your doubt? i wasn’t expecting that.

#7

bro in doubt section there is option chat with TA ,there the name of the TA is written

#9

doing i am struck making pair of node* , horizontal distance in five minute i will send

#10

Submit this


vector<int> verticalOrder(Node *root)
{
    //Your code here
        map<int,vector<int>> m;
        queue<pair<Node*,int>> q;
        q.push({root,0});
        while(q.empty()!=true)
        {
            auto temp=q.front();
            Node * curr=temp.first;
            int hd=temp.second;
            m[hd].push_back(curr->data);
            q.pop();
            if(curr->left)
            q.push({curr->left,hd-1});
            if(curr->right)
            q.push({curr->right,hd+1});
            
        }
       vector<int> v,v1; 
        for(auto itr:m)
        {
        v=itr.second;
        for(int x:v)
        v1.push_back(x);
        }
        return v1;
        
}

Will need stack to do bfs traversal so did it, getting accepted too.

#11
#12

i too got it it took a while

#13

Sahi sahi, now is it getting accepted na?

#14

yes it got accepted @mr.encoder

#15

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.