Bhaiya bhaiya 🤟🤟

Did by applying all the traversal techniques : Thanks Striver a lot 🙂 class Solution { public: void postOrder(TreeNode* root,map &mapping,int vertical,int level) { if(root==nullptr)return; if(root->left)postOrder(root->left,mapping,vertical-1,level+1); if(root->right)postOrder(root->right,mapping,vertical+1,level+1); mapping[vertical][level].insert(root->val); } void inOrder(TreeNode* root,map &mapping,int vertical,int level) { if(root==nullptr)return; if(root->left)postOrder(root->left,mapping,vertical-1,level+1); mapping[vertical][level].insert(root->val); if(root->right)postOrder(root->right,mapping,vertical+1,level+1); } void preOrder(TreeNode* root,map &mapping,int vertical,int level) { if(root==nullptr)return; mapping[vertical][level].insert(root->val); if(root->left)postOrder(root->left,mapping,vertical-1,level+1); if(root->right)postOrder(root->right,mapping,vertical+1,level+1); } void levelOrder(TreeNode* root,map &mapping) { if(root==NULL)return; queue queue; queue.push({root,{0,0}}); while(!queue.empty()) { int size=queue.size(); for(int i=0;ival); if(node->left)queue.push({node->left,{vertical-1,level+1}}); if(node->right)queue.push({node->right,{vertical+1,level+1}}); } } } vector verticalTraversal(TreeNode* root) { if(root==nullptr)return {}; map mapping; /* using preOrder Traversal preOrder(root,mapping,0,0); using inOrder Traversal inOrder(root,mapping,0,0); using postOrder Traversal postOrder(root,mapping,0,0); using level order Traversal */ levelOrder(root,mapping); vector answers; for(auto mapp:mapping) { vector answer; for(auto tt:mapp.second) for(auto inner:tt.second) answer.push_back(inner); answers.push_back(answer); } return answers; } };

i done ,All

CN is overrrrrrated

@@divyanshuchaudhari3257 the content is good but still has many shortcomings regarding platform and services.

@@ravindrabarthwal how much it costs?

In their CP course, they don't have any module on binary trees and binary search trees.

@@gowreeManohar don't buy man litreally even I experienced buy nothing from Coding ninjas I buyed 16k web dev course it's totally not worth even content is not there totally for a student worst platform coding ninjas

any reason for not using multiset?

@@sidarthroy815 on gfg we have to return a vector ,that's the reason .

@@sidarthroy815 visit this question on gfg

yess, I tried on my own upto some extent but wasted 6-7 hours, really amazing problem

took me 50 minutes of hardcore focus to solve this one, and still was only able to beat 6% all Solution time. Also had to look syntax 2 or 3 times. very difficult problem indeed.

CAN you explain col.insert(col.end(),q.second.begin(),q.second.end()); this line plzz bro

@@codding32world50 yeah this line is confusing

@@codding32world50 this means you are inserting all the elements of multimap at the end of the col vector

why can't we use inorder for the gfg probem? My Tc are not getting passed in GFG private: void preOrder(Node* node,int col,map &mp){ if(node==nullptr){ return; } if(mp.find(col)==mp.end()){ mp[col]={node->data}; } else mp[col].push_back(node->data); // or mp[col].push_back() if(node->left!=nullptr) preOrder(node->left,col-1,mp); if(node->right!=nullptr) preOrder(node->right,col+1,mp); } public: //Function to find the vertical order traversal of Binary Tree. vector verticalOrder(Node *root) { map mp; preOrder(root,0,mp); vector ans; //traverse in map and store it in ans; say ans.push_back(mp[0]) and so on..... for(auto it:mp){ // sort(it.second.begin(),it.second.end()); for(auto ele:it.second){ ans.push_back(ele); } } return ans; }

@@atulwadhwa192 For each vertical level, your vector should be filled from top to bottom, this thing will not happen with this code

you are correct..

nah striver is just testing us if we are paying attention

@@dom47 "not a bug, but a feature" type comment 😂

thanks man

Or unordered map and queue

same brother

Correct bro, i have assumed map to work as o(1) due to java

@@takeUforward Ok, got it.

@@JohnWick-kh7ow so what would it actually be for C++ solution?

@@sans.creates O(N*logN*logN*logN) will be time complexity for C++ solution. We are using two maps and one multiset and we are traversing each node.

Shouldnt the time complexity be same for Java because TreeMap also takes O(logn)??

Vector will distort the sorted wala property..

@@takeUforward We r going level by level, first it will push_back node at level 0, then for level 1, then for level 2 and so on.. So by default it's in order. U can check it once again, otherwise I will post code tomorrow

@@jashanbansal2613 if in the same vertical, and same level you have 9 first and then 8, your vector will store 9,8 But should be 8,9 :)

@@takeUforward Thanks for taking time to reply Man :)

@@takeUforward bhaiya if we iterate from backwards while traversing in the map finally, will that work ?

it's not allowed because std::map keys must be of a type that supports comparison for equality and ordering.

mapnodes; nodes[x][y].push_back(head->data); Can you explain how the value is getting stored? I am not getting how this statement "nodes[x][y].push_back(head->data);" is working internally? TIA

@@jaspreetmehra572 if you use this statement then the node will get inserted in its (vertical,level) , u might not understand what i have typed xD, but once visualise x and y ...x=p.second.first ,y=p.second.second ,u might understand

This code is wrong bro. It will include values with same level and vertical but doesn't include values with same vertical and different levels in a same array.

for (auto q: p.second) will run number of horizontal levels we have whereas col.insert(col.end(), q.second.begin(), q.second.end()) will insert number of elements which are present on [vertical level] [horizontal level]

can also do this way vector res; for (auto itr1 = nodes.begin(); itr1 != nodes.end(); itr1++) { vector temp; for (auto itr2 = itr1->second.begin(); itr2 != itr1->second.end(); itr2++) { for (auto itr3 = itr2->second.begin(); itr3 != itr2->second.end(); itr3++) { temp.push_back(*itr3); } } res.push_back(temp); } return res;

Can u pls share?

@@tharundharmaraj9045 I did the similar thing void preorder(TreeNode* root,int curr,int ver,unordered_map &m){ if(!root) return; m[curr].push_back({ver,root->val}); preorder(root->left,curr-1,ver+1,m); preorder(root->right,curr+1,ver+1,m); } vector verticalTraversal(TreeNode* root) { unordered_map m; preorder(root,0,0,m); vector v; for(auto i:m){ v.push_back({i.first,i.second}); } sort(v.begin(),v.end()); vector ans; for(auto i:v){ vector temp; sort(i.second.begin(),i.second.end()); for(auto j:i.second){ temp.push_back(j.second); } ans.push_back(temp); } return ans; }

col.insert(col.end(), p.second.begin(), p.second.end()); please explain this line

@@sawantanand3681 basically you are adding at the end of your vector "col" map.first.begin ie say you have an element {1,2} in the map inside the outer map you declared...then map.first.begin refers to 1 and map.first.end refers to 2. Alternatively you can do it this way if you want for(auto q: p.seond) //so q refers to your multiset now while p was referring to your map above. {col.push_back(q)}; } ans.push_back(col); } return ans; } };

@@shauryashekhar what if there is only 1 element on a level and not two? will the map.first.begin and map.first.end both not print the same value twice because both the pointers will be on the same value?!?

you should use - - x and ++y

No because at time of insertion you need to maintain level also and there can be more than one values of vertical lines at a particular level.

Yeah I think then we just need to use map

What is order of overlapping ?

It won’t store sorted na if on a level there are multiple overlap.

i think they are not storing level also they are only storing vertices(-1,0,+1..) and the nodes at respective vertices

Usually hashmap works in o(1) in java, hence i said you can compute map wala khud se depending on language you using.

col is having data type as int and not that of any 1d vector or set, we cannot pushback

bhai 2 se jada values bhi ho skti hai ek vertical pe

x axis is horizontal a s you know