L21. Vertical Order Traversal of Binary Tree | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@ng3w462]

Bhaiya bhaiya 🤟🤟

[@deepanshjohri3997]

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; } };

[@KanhaiyaLal-yv3sq]

i done ,All

[@vashishthsharma4411]

if you are solving this problem on GFG change two things 1. instead of using multiset use a vector. 2. copy the vector of vector (ans) into a 1d vector ,return the 1d vector. at last thank u Raj bhaiya , great work.

[@sidarthroy815]

any reason for not using multiset?

[@vashishthsharma4411]

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

[@vashishthsharma4411]

@@sidarthroy815 visit this question on gfg

[@sreyashisaha6852]

@@sidarthroy815 multiset stores elements in ascending order, which may invalidate the condition that the elements need to be stored according to level order traversal.

[@MischievousSoul]

One of the hardest question in the whole playlist.. Took a whole day to understand and write the code.. But ig its fair to not rush and just devote the req time to some questions..

[@AppaniMadhavi]

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

[@valdidar]

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.

[@user.princegaming]

i did it in one shot beat 100 %

[@riteshhere8611]

@@user.princegaming same here done within 1hr here is my code(beats 100%) :- vector verticalTraversal(TreeNode* root) { vector res; if(root==nullptr) return res; queue q; map m; q.push({root,0}); while(!q.empty()){ int n = q.size(); vector temp; for(int i =0;ileft){ q.push({node.first->left,node.second-1}); } if(node.first->right){ q.push({node.first->right,node.second+1}); } temp.push_back({node.second,node.first->val}); } sort(temp.begin(),temp.end()); for(int i =0;isecond); } return res; }

[@bestdeal3385]

for those having difficulty in the last part can use this code segment ( just elaborated a bit for easy understanding ) 😊😊 vector ans; for(auto it:m) { vector v; for(auto t:it.second) { for(auto x:t.second) { v.push_back(x); } } ans.push_back(v); } return ans; }

[@jaspreetmehra572]

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

[@madhabkafle8898]

@@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

[@jerryraphy739]

[@XanderSR]

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.

[@aayushgoswami8632]

for(auto p:nodes){ vectorcol; for(auto q:p.second){ for(int it: q.second){ col.push_back(it); } } ans.push_back(col); } use this if u didin't understood col.insert thing.

[@dhanushrajan6280]

thanks man

[@ok-sb1ts]

Bro don't you think it will increase the time complexity of code

[@RamNarayan-B]

@@ok-sb1ts No, Col.insert(col.end(), q.second.begin(), q.second.end()) in the video is literally translated to the piece of code shared in this comment. Code is made simpler for easy understanding letting us know we insert all the elements in one shot, but internally, the elements are iterated and inserted one by one.

[@ravindrabarthwal]

I'm enrolled in Coding Ninjas Competitive Programming Premium course. Your content has much more depth than CN.

[@divyanshuchaudhari3257]

CN is overrrrrrated

[@ravindrabarthwal]

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

[@gowreeManohar]

@@ravindrabarthwal how much it costs?

[@siddharth7261]

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

[@Zunan263]

@@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

[@014_anurag2]

Wow after this wonderful explanation!! preorder approach became too easy. Here is the code :- void preorder(TreeNode* node,int vertical,int level,map &nodes){ if(node == nullptr) return; nodes[vertical][level].insert(node->val); preorder(node->left,vertical-1,level+1,nodes); preorder(node->right,vertical+1,level+1,nodes); } vector verticalTraversal(TreeNode* root) { map nodes; preorder(root,0,0,nodes); vector ans; for(auto p:nodes){ vector col; for(auto q:p.second){ col.insert(col.end(),q.second.begin(),q.second.end()); } ans.push_back(col); } return ans; }

[@codding32world50]

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

[@sageoustheory1957]

@@codding32world50 yeah this line is confusing

[@mjmusic65]

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

[@anonymousvoid6356]

Hey everyone! Welcome back to the channel. I hope you guys are doing well! My mind gets fresh whenever i hear this from strivers mouth.

[@soumikdutta7867]

The GFG variant of this question is a bit easy. In the GFG variant you don't need to sort the elements, just add the elements in the ans. as it is in the tree.

[@atulwadhwa192]

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; }

[@vijaymalviya23]

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

[@dikshasoni52a98]

i think this is the hardest question of this playlist till now...... it really required like 1 day to understand this and code it.

[@jashanbansal2613]

Can be solved using map We r going level by level only, so nodes would be inserted from top to bottom, therefore no need to maintain level

[@takeUforward]

Vector will distort the sorted wala property..

[@jashanbansal2613]

@@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

[@takeUforward]

@@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 :)

[@jashanbansal2613]

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

[@AyushGupta-kp9xf]

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

[@nopecharon]

4:37 There is a small typo, the co-ordinates of the rightmost node is actually (2, 2) not (1, 2)

[@jewelchowdhury9752]

you are correct..

[@dom47]

nah striver is just testing us if we are paying attention

[@SomanAnshuman]

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

[@subhamtulshan4023]

Here the Time Complexity will be o(nlogN) , as we are using TreeMap and each operation in treeMap takes logN time. We can use DLL to solve it in O(N). where each node in DLL is like (data -> list of element, next -> points to the next verticle, prev-> points to the previous vertical)

[@knowledgeworld6951]

Or unordered map and queue

[@fahrenheit2109]

absolutely amazing explanation, learned a lot more than tree traversal in this video (my STL is not the best)

[@vaibhavsingh4108]

same brother

[@lone_wolf7721]

man the explaination is masterclass.. hats off to you .. at first i have a problem but as you suggested to dry run i have done and now its crystal clear

[@Negijicoder]

i've done it myself by using bfs(level order) and preorder..(dfs, and used tuple to store all values.. like vector vec; )

[@Dipanshutripathi2407]

Before wathcing the video I could not solve the problem by looking the solution but after watching video i could solve the problem on my own .

[@harshbhagwani7769]

PYTHON SOLN FOR VERTICAL ORDER TRAVERSAL class Solution: def __init__(self): self.values={} def vertical_order(self,root,x,y): if root is None : return if x in self.values : self.values[x].append((y,root.val)) else : self.values[x]=[(y,root.val)] self.vertical_order(root.left,x-1,y+1) self.vertical_order(root.right,x+1,y+1) def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: self.vertical_order(root,0,0) result=[] for x in sorted(self.values.keys()): column=[i[1] for i in sorted(self.values[x])] result.append(column) return result

[@chandrachurmukherjeejucse5816]

Solved myself without watching the solution using map of map. got a dopamine hit. Thanks striver.

[@gitanjalikumari9262]

Thank you so much for explaining the C+++ code..after lot of searching I found this video and it's awesome

[@Progamer-fq8st]

We can also use map

[@iamnottech8918]

now I know why some said donot use java for cp ,c++ is a life saver

[@shlokdubey8220]

For those having difficulty in understanding map and multisets, check this out, logic is same..(used sorting) static bool comp(vector &a,vector &b) { if(a[0]==b[0] && a[1]==b[1]) { return a[2]left); temp.push_back({temp[index][0]+1,temp[index][1]-1,node->left->val}); } if(node->right) { q.push(node->right); temp.push_back({temp[index][0]+1,temp[index][1]+1,node->right->val}); } index++; } sort(temp.begin(),temp.end(),comp); vector v; v.push_back(temp[0][2]); int cur_col=temp[0][1]; for(int i=1;i

[@coding8000]

Understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, Ctr + right arrow, for shifting the chapter of ads in video

[@noobchess2516]

easy solution that you can understand using custom data structure . idea - custom datastructure to store node value, x,y coordinate and then sort it as per our required . (sort in termss of x coordinate if same, sort in terms of y coordinate, if same ,value compare all in ascending order) then just return vector. struct point{ int value; int x; int y; }; void travel(TreeNode*root,int x,int y,vector&save){ if(root==NULL){ return; } point a ; a.value=root->data; a.x =x; a.y=y; save.push_back(a); travel(root->left,x-1,y+1,save); travel(root->right,x+1,y+1,save); } bool compare(point a,point b){ if(a.x!=b.x){ return a.x

[@sudhanshukumar3391]

I understand this question partially. When i understand the problem statement , then at same moment I guessed that this problem would be leetcode hard category, And yes it is.

[@Weirdvloggertrue]

Great explaination!❤️ Waiting for BSTs... 😌

[@sahilkumarsingh8517]

Understood 😁 //using inOrder Traversal code class Solution { public: void inOrder(TreeNode* root, int x, int level, map &map) { if(root==NULL) return; inOrder(root->left, x-1, level+1, map); map[x][level].insert(root->val); inOrder(root->right, x+1, level+1, map); } vector verticalTraversal(TreeNode* root) { if(root == NULL) return {}; map map; inOrder(root, 0, 0, map); vector ans; for(auto it:map) { vector col; for(auto p:it.second) col.insert(col.end(), p.second.begin(), p.second.end()); ans.push_back(col); } return ans; } };

[@sawantanand3681]

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

[@shauryashekhar]

@@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; } };

[@virusdgamer8804]

@@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?!?

[@anmolswarnkar7707]

I was able to solve this one myself, but instead of using multisets, I sorted the individual columns later (based on the values of nodes on the same level).

[@tharundharmaraj9045]

Can u pls share?

[@DimensionalDriftYoru]

@@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; }

[@shwetanksingh5208]

//Another approach using tuple to take row also in picture along with line class Solution { public: static bool comparator(tuple t1,tuple t2)//line,row,value { int l1=get(t1),l2=get(t2),r1=get(t1),r2=get(t2),val1=get(t1),val2=get(t2); if(l1nodeVal> queue qu; // line> qu.push(make_pair(root,0)); pair temp; int row = 0; while(!qu.empty())//level order traversal { int size = qu.size(); while(size--) { temp = qu.front(); qu.pop(); vect.push_back(make_tuple(temp.second,row,temp.first->val)); if(temp.first->left) qu.push(make_pair(temp.first->left,temp.second-1)); if(temp.first->right) qu.push(make_pair(temp.first->right,temp.second+1)); } row++; } sort(vect.begin(),vect.end(),comparator); int currLine = get(vect[0]);//line number of first tuple vector thisLineVals; for(auto p:vect)//p is a tuple { if(get(p)==currLine) { thisLineVals.push_back(get(p)); } else { currLine = get(p); ans.push_back(thisLineVals); thisLineVals.clear(); thisLineVals.push_back(get(p)); } } if(!thisLineVals.empty())//if currLine didn't change and thisLineVals left to be pushed in ans { ans.push_back(thisLineVals); } return ans; } };

[@pranavmisra5870]

Brilliant explanation and hats off to whoever though of this solution.

[@rushidesai2836]

Good question. Its mostly about visualizing how the node data is stored in the root map.

[@symbol767]

I did this in Python. I used minHeap with a tuple, I thought I had to make a class to modify/overload some minHeap functionality, but I didn't need to. So you can just use a minHeap without making a new "VerticalLevel" class class VerticalLevel: def __init__(self): self.minHeap = []; def add(self, val, level): heapq.heappush(self.minHeap, (val, level)); def remove(self): return heapq.heappop(self.minHeap); class Solution: def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: result = []; queue = deque(); queue.append((root, 0, 0)); verticalHeap = {}; minLevel = float('inf'); maxLevel = -float('inf'); while len(queue) > 0: levelSize = len(queue); for _ in range(levelSize): node, level, vertical = queue.popleft(); minLevel = min(minLevel, vertical); maxLevel = max(maxLevel, vertical); if vertical not in verticalHeap: verticalHeap[vertical] = VerticalLevel(); verticalHeap[vertical].add(level, node.val) if node.left: queue.append((node.left, level + 1, vertical - 1)); if node.right: queue.append((node.right, level + 1, vertical + 1)); for level in range(minLevel, maxLevel + 1): print(level) currentLevel = verticalHeap[level]; # Pop all elements off the modified minHeap and add it into a tempLevel array tempLevel = []; while len(currentLevel.minHeap) > 0: level, value = currentLevel.remove(); tempLevel.append(value); # Now append the tempLevel array into the result array result.append(tempLevel); return result;

[@ShivamKanojia-oz8ph]

Using Inorder class Solution { public: void traversal(TreeNode* root, int vertical, int level, map &nodes) { if (root == NULL) return; traversal(root->left, vertical - 1, level + 1, nodes); nodes[vertical][level].insert(root->val); traversal(root->right, vertical + 1, level + 1, nodes); } vector verticalTraversal(TreeNode* root) { vector ans; map nodes; traversal(root, 0, 0, nodes); for (auto i : nodes) { vector col; for (auto j: i.second) { col.insert(col.end(), j.second.begin(), j.second.end()); } ans.push_back(col); } return ans; } };

[@lifehustlers164]

Completed 22/54(40% done) !!!

[@mriduljain1981]

i did the 90% question myself i just couldnot find out which datastructure to use i am super happy about it ..................

[@Allinoneinlivi]

Without taking extra level order mapmp; queueq; q.push({root,0}); while(!q.empty()){ auto p=q.front(); q.pop(); int size=q.size(); node* temp = p.first; mp[p.second].insert(temp->val); if(temp->left){ q.push({temp->left,p.second-1}); } if(temp->right){ q.push({temp->right, p.second+1}); } } for(auto x: mp){ for(auto y:x.second){ cout

[@peter9759]

Lovely explanation yaar itne pyaar se kisi ne nhi sikhaaya

[@sanjayp.m7008]

can just use a pqval>> and perform a dfs traversal and push all the elements updating the col and row and finally pop from the pq and push into ans and return ans, :)

[@SumitKeshariMCS]

Solved on my own. Then watched your video. Thanks striver for quality content. here is my code: class Solution { public: vector verticalTraversal(TreeNode* root) { vectorans; if(root==NULL) return ans; queueq; q.push({0,{0,root}}); mapmp; while(!q.empty()) { auto it = q.front(); q.pop(); int hd = it.first; int level = it.second.first; TreeNode* node = it.second.second; mp[hd][level].insert(node->val); if(node->left) q.push({hd-1,{level+1,node->left}}); if(node->right) q.push({hd+1,{level+1,node->right}}); } for(auto it = mp.begin();it!=mp.end();it++) { vectortemp; for(auto i = it->second.begin();i!=it->second.end();i++) { for(auto ii = i->second.begin();ii!=i->second.end();ii++) { temp.push_back(*ii); } } ans.push_back(temp); } return ans; } };

[@AdityaKumar-be7hx]

Could we have just used "mapint>> nodes"?

[@Pooja-lm5yj]

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

[@rohan8758]

Understood, great explanation Striver!

[@chirag6475]

Thank you Striver Bhaiya. You're a inspiration to me.

[@JohnWick-kh7ow]

Why time complexity is O(N*logn)? we are using map > So it should be O(N*logN*logN*logN). please explain.

[@takeUforward]

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

[@JohnWick-kh7ow]

@@takeUforward Ok, got it.

[@sans.creates]

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

[@JohnWick-kh7ow]

@@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.

[@divyambhutani6229]

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

[@dhananjayvaish3276]

// for those having difficulty in last part of soln , i have named variables accordingly , you can check and understand vector verticalTraversal(TreeNode* root) { // {vertical , {level , node->val}} map m; // {node , {vertical , level}} queue q; q.push({root , {0 , 0}}); while(!q.empty()) { auto it = q.front(); q.pop(); TreeNode* node = it.first; int vertical = it.second.first; int level = it.second.second; m[vertical][level].insert(node -> val); if(node -> left) q.push({node -> left , {vertical - 1 , level + 1}} ); if(node -> right) q.push({node -> right , {vertical + 1 , level + 1}}); } vectorans; for(auto oneVertical : m) { // vec is a vector of int to store one complete vertical . vectorvec; for(auto levelAndSet : oneVertical.second) { for(auto setElement : levelAndSet.second) { vec.push_back(setElement); } } ans.push_back(vec); } return ans; }

[@VishalGupta-xw2rp]

Yes it was indeed helpful. Today only i watched the stl of Striver so Like why we are using insert, key value pair and it being sorted and all duplication are allowed. I got the in depth meaning. It's actually like I'm beginning to understand the meaning of life. *Striver is Saviour* ♥️

[@tusharpant903]

muje col.end ka concept smjh n aya could u plz explain

[@VishalGupta-xw2rp]

.end() you can think like size is 5 So indexing will be 0 to 4. .end() will be like 5 it's the end of array

[@coding8000]

thanks!!!!

[@dhananjayvaish3276]

@@coding8000 you're welcome

[@shivanisisodia6189]

thankgod first time he has taken Queue diagram as a queue not as a stack like in other videos, there is so much confusion bcoz of that and difficult to remember also for future.

[@AyushSachan2211]

Tip: You should have taken 'y' as vertical and 'x' as level. Then it will be more easy to visualise in the coordinate system.

[@bhaveshkumar6842]

Bro, trace the given code completely and you'll find his method as the most appropriate.

[@debasmitamallick6489]

visualize this as x and y coordinate

[@namansharma7328]

@@debasmitamallick6489 yes correct.

[@namansharma7328]

vertical lines are made on x-axis buddy. Consider them as axes as told by @debasmita

[@apmotivationakashparmar722]

Thank you so much Striver.

[@mayurbhor2231]

The problem can be solved in O(N) time without multiset , if the order of overlapping elements is not necessary to be in ascending order

[@adityasai550]

Yeah I think then we just need to use map

[@tushar7305]

What is order of overlapping ?

[@akshikaagarwal2437]

Using inorder traversal: void inorder(TreeNode* root, map& m, int row, int vertical) { if (!root) { return; } inorder(root->left, m, row + 1, vertical - 1); m[vertical][row].insert(root->val); inorder(root->right, m, row + 1, vertical + 1); } vector verticalTraversal(TreeNode* root) { vector ans; if (!root) { return ans; } map mpp; inorder(root, mpp, 0, 0); for (auto m : mpp) { vector temp; for (auto s : m.second) { temp.insert(temp.end(), s.second.begin(), s.second.end()); } ans.push_back(temp); } return ans; }

[@girikgarg8]

Clean Code in C++ using level order traversal: class node{ public: TreeNode *treeNode; int line; int level; node(TreeNode *nd,int _line,int _level):treeNode(nd),line(_line),level(_level) {} }; class Solution { public: static bool comp(node &n1,node &n2){ if (n1.level!=n2.level) return n1.levelvalval; } vector verticalTraversal(TreeNode* root) { map mp; node n1(root,0,0); queue q1; q1.push(n1); while (!q1.empty()){ int n=q1.size(); while (n--){ node temp=q1.front(); q1.pop(); int currLine=temp.line; int currLevel=temp.level; TreeNode *tp=temp.treeNode; mp[currLine].push_back(temp); if (tp->left) q1.push(node(tp->left,currLine-1,currLevel+1)); if (tp->right) q1.push(node(tp->right,currLine+1,currLevel+1)); } } vector ans; for (auto u:mp){ sort(begin(u.second),end(u.second),comp); vector temp; for (auto v:u.second) temp.push_back(v.treeNode->val); ans.push_back(temp); } return ans; } };

[@babulalyadav4305]

00:02 Introduction to vertical order traversal in binary tree 02:13 Understand the concept of vertical order traversal in a binary tree 04:32 Traversing and assigning verticals and levels to every node 06:39 Using multiset to store multiple notes for each level 08:51 Understanding the vertical order and level change during level order traversal 10:49 Vertical order traversal involves tracking node positions 12:49 Storing vertical orders using data structures 15:04 Explaining vertical order traversal in Java 17:00 Explanation of time and space complexity for vertical order traversal 18:38 Subscribe for upcoming series Crafted by Merlin AI.

[@aadityavaid6818]

I did this using min-heap priority queue ds and preorder traversal I stored the values like this {col, row, value} to have the left most guys on the top of PQ ------->1 CHALLENGE I FACED: I was trying to pass PQ to the preorder function but it gives the error: "the type-id must not have a name". ------->SOLUTION TO ERROR: we have to keep the greater. Those of u face problem in passing min-heap in a function can try this. TC: O(NlogN) SC: O(N) {for priority queue} Code: class Solution { void preorder(TreeNode* node, priority_queue &pq, int row, int col){ if(node==NULL) return; pq.push({col,row,node->val}); preorder(node->left, pq, row+1, col-1); preorder(node->right, pq, row+1, col+1); } public: vector verticalTraversal(TreeNode* root) { priority_queue pq; // vector ans; preorder(root, pq, 0, 0); int size= pq.size(); int colref= pq.top()[0]; vector temp; for(int i=0; i

[@techmelon7]

Absolute gem!

[@utkarshshukla3567]

At 4:22 the coordinates of 10 should be (2,2)

[@rishabhshairy972]

great explanation

[@stylewithsmriti]

This approach takes O(n*logn) time complexity. Can you please make a video on efficient solution that takes O(n)?

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@herculean6748]

Can someone please explain this a bit (Inner for loop, how many times will it run) for (auto p: nodes) { vector < int > col; for (auto q: p.second) { col.insert(col.end(), q.second.begin(), q.second.end()); } ans.push_back(col); }

[@rishabhgupta9846]

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]

[@rishabhgupta9846]

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;

[@saileshsirari2014]

Using 3 data structures , level order traversal, we need to sort same distance and level nodes. public List verticalTraversal(TreeNode root) { List ans = new ArrayList(); solve(root,ans); return ans; } private void solve(TreeNode root,List ans){ Map map = new TreeMap();//distance to list of nodes map, final list for each dist Map distMap = new HashMap(); // each node and its dist, need for child dist MaplevelMap = new HashMap();// each node and its level Queue q = new LinkedList(); q.add(root); q.add(null); int dist =0; int level =0; List l = new ArrayList(); l.add(root); map.put(0,l); distMap.put(root,0); levelMap.put(root,0); level++; while(!q.isEmpty()){ TreeNode node = q.poll(); if(node==null){ if(!q.isEmpty()) q.add(null); level++; continue; } //dist of parent dist = distMap.get(node); if(node.left!=null){ // map.get() q.add(node.left); distMap.put(node.left,dist-1); levelMap.put(node.left,level+1); addToList(map,node.left,dist-1,level+1,levelMap); } if(node.right!=null){ q.add(node.right); distMap.put(node.right,dist+1); levelMap.put(node.right,level+1); addToList(map,node.right,dist+1,level+1,levelMap); } } for (Map.Entry item : map.entrySet()) { Integer key = item.getKey(); List list = item.getValue(); List listAns = new ArrayList(); for(int i=0;i{ return a.val-b.val; }); list.addAll(sub); }

[@ishangujarathi10]

you make leetcode hard problems easy to understand!!!! tysm

[@4747surya]

Using inOrder class Solution { public List verticalTraversal(TreeNode root) { List ans = new ArrayList(); if(root == null){ return ans; } TreeMap treeMap = new TreeMap(); inOrder(root,treeMap, 0,0); for(TreeMap ys: treeMap.values()){ ans.add(new ArrayList()); for(PriorityQueue nodes: ys.values()){ while(!nodes.isEmpty()){ ans.get(ans.size()-1).add(nodes.poll()); } } } return ans; } private void inOrder(TreeNode root, TreeMap treeMap, int vl, int tl){ if(root == null){ return; } if(!treeMap.containsKey(vl)){ treeMap.put(vl, new TreeMap()); } if(!treeMap.get(vl).containsKey(tl)){ treeMap.get(vl).put(tl, new PriorityQueue()); } treeMap.get(vl).get(tl).offer(root.val); // left call inOrder(root.left, treeMap,vl-1,tl+1); // right call inOrder(root.right, treeMap,vl+1,tl+1); } }

[@sahilkhan_cs50]

class Solution { public: void inorder(TreeNode* root,int vertical,int level,map& mp) { if(root==NULL) return; inorder(root->left,vertical-1,level+1,mp); //work to be done...multiset keeps elements in sorted order mp[vertical][level].insert(root->val); inorder(root->right,vertical+1,level+1,mp); } vector verticalTraversal(TreeNode* root) { //ds //pass the vertical and the level of the nodes as a parameter in inorder traversal //hence while traversing in inorder fashion,the parameters-vertical and level will be used //store the (vertical,level,val) in a ds..now while retrieving the val from the ds,we need to print the elements of lowest vertical first(sort vertical)...for a given vertical, sort level,for a given level add all the elements val to the vertical order traversal..that sorting and all will take o(nlog n )time.. //hence it is better to use map ...while inserting an element it will take logN+logN+logN =3logN time complexity //while retrieving val using the ds,we require o(n) for traversing the outer map and o(m) for traversing the inner map...and for the multiset o(1) as accessing its only it.begin() and it.end() ....so overall tc is o(N)---NO OF ELEMENTS IN TREE vector answer; map mp; inorder(root,0,0,mp); //iterate over mp for(auto vertical:mp){ //vertical is a map //sorted order vector col; for(auto level:vertical.second){ col.insert(col.end(),level.second.begin(),level.second.end()); } answer.push_back(col); } return answer; } };

[@sanmeshkakade5368]

If you are solving on leetcode and if you are using java to solve, you can't use TreeSet as it won't contain duplicates, you will have to use List and sort it before appending to the final answer list.

[@DeepakGupta-ko8lh]

Below is the java code using preorder traversal: class Solution { public List verticalTraversal(TreeNode root) { //Here i am using preorder traversal approach, we can also do it using level order traversal TreeMap tm=new TreeMap(); vertTraversal(root, tm, 0, 0); List ans=new ArrayList(); for(TreeMap subMap: tm.values()){ ArrayList temp=new ArrayList(); for(List al: subMap.values()){ Collections.sort(al); temp.addAll(al); } ans.add(temp); } return ans; } public void vertTraversal(TreeNode root, TreeMap tm, int row, int col){ if(root==null) return; if(!tm.containsKey(col)) tm.put(col, new TreeMap()); if(!tm.get(col).containsKey(row)) tm.get(col).put(row, new ArrayList()); tm.get(col).get(row).add(root.val); vertTraversal(root.left, tm, row+1, col-1); vertTraversal(root.right, tm, row+1, col+1); } }

[@captain-ne8qy]

if(!tm.containsKey(col)) tm.put(col, new TreeMap()); if(!tm.get(col).containsKey(row)) tm.get(col).put(row, new ArrayList()); bhai agr( row, col ) kisi level p 2 node ka equal ho tb wo value( node.data )kaise insert krenge???? 5:17 @ ( row, col ) = (0,2) there are two node 9 & 10???? bhai kaise krenge

[@shradhaydham4745]

using preorder traversal code is here /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector verticalTraversal(TreeNode* root) { vectorans; stackst; mapmp; st.push({root,{0,0}}); while(!st.empty()) { auto temp=st.top(); st.pop(); TreeNode* node=temp.first; int x=temp.second.first; int y=temp.second.second; mp[x][y].insert(node->val); if(node->right) st.push({node->right,{x+1,y+1}}); if(node->left) st.push({node->left,{x-1,y+1}}); } for(auto i :mp) { vectorv; for(auto j:i.second) { v.insert(v.end(),j.second.begin(),j.second.end()); } ans.push_back(v); } return ans; } };

[@albatrossgeez6637]

understood.................thanks bhaiya for the amazing videos

[@lucifersamrat6280]

tough but it was very great explanation

[@gauravchauhan7412]

//CODE FOR PREORDER- class Solution { private: mapnodes; void preorder(TreeNode* root, int x , int y){ if(root==NULL) return; nodes[x][y].insert(root->val); preorder(root->left, x-1, y+1); preorder(root->right, x+1, y+1); } public: vector verticalTraversal(TreeNode* root) { preorder(root, 0, 0); vectorans; for(auto p1:nodes){ vectortemp; for(auto p2:p1.second) temp.insert(temp.end(), p2.second.begin(), p2.second.end()); ans.push_back(temp); } return ans; } };

[@rakshayadav1892]

Python code: class Solution: def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: st=[(root,0,0)] ans=[] while st: t=st.pop() ans.append((t[0].val,t[1],t[2])) lvl=t[1]+1 if t[0].left: st.append((t[0].left,lvl,t[2]-1)) if t[0].right: st.append((t[0].right,lvl,t[2]+1)) ans=sorted(ans,key=lambda i:i[1]) ans=sorted(ans,key=lambda i:i[2]) i=0 fin=[] t=[] a=[] print(ans) while i

[@cinime]

Understood! Such an amazing explanation as always, thank you very much!!

[@AnkushMallickOriginal]

Solution: (Vertical Order Traversal of Binary Tree - By Inorder Traversal) void inorder(TreeNode *node, int x, int y, map &mpp){ if(node == NULL){ return; } inorder(node->left, x - 1, y + 1, mpp); mpp[x][y].push_back(node->data); inorder(node->right, x + 1, y + 1, mpp); } vector verticalOrderTraversal(TreeNode *root) { // Write your code here. map mpp; vector ans; if(root == NULL){ return ans; } inorder(root, 0, 0, mpp); for(auto p: mpp){ for(auto q: p.second){ for(int it: q.second){ ans.push_back(it); } } } return ans; }

[@mohdkashif9830]

I think we can do it this way too without using hashmap,set and all that i.e just by using a comparator function. class Solution { public: struct node { TreeNode* n; int row; int col; node(TreeNode* nodec, int r, int c) { n = nodec; row = r; col = c; } }; // Custom comparator simplified using tuple comparison static bool comp(const vector& a, const vector& b) { return tie(a[2], a[1], a[0]) < tie(b[2], b[1], b[0]); } vector verticalTraversal(TreeNode* root) { if (!root) return {}; queue q; q.push(node(root, 0, 0)); vector vec; int minCol = 0, maxCol = 0; // Level-order traversal with row and col tracking while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { node el = q.front(); q.pop(); vec.push_back({el.n->val, el.row, el.col}); minCol = min(minCol, el.col); maxCol = max(maxCol, el.col); if (el.n->left) q.push(node(el.n->left, el.row + 1, el.col - 1)); if (el.n->right) q.push(node(el.n->right, el.row + 1, el.col + 1)); } } // Sort by column, then row, then node value sort(vec.begin(), vec.end(), comp); // Prepare result vector and resize based on min and max column indices vector ans(maxCol - minCol + 1); for (auto& v : vec) { int colIndex = v[2] - minCol; // Normalize column index ans[colIndex].push_back(v[0]); } return ans; } };

[@bhashkarbelwal4116]

what an easy clarification yar man

[@vibewithalexa]

class Solution { public: map m; void traversal(TreeNode* root , int x , int y){ if(root == NULL) return; m[y].push_back({x,root->val}); traversal(root->left,x+1,y-1); traversal(root->right,x+1,y+1); } vector verticalTraversal(TreeNode* root) { traversal(root,0,0); vector res; for ( auto it : m) { vector v = it.second; sort(v.begin(),v.end()); vector temp ; for( auto k : v){ temp.push_back(k.second); } res.push_back(temp); } return res; } };

[@jaipurite8119]

If there are multiple nodes passing through a vertical line, then they should be printed as they appear in level order traversal of the tree. vector verticalOrder(Node *root) { //Your code here if(!root) return {}; map nodes; queue q; q.push({root, {0, 0}}); while(!q.empty()) { auto qe = q.front(); q.pop(); Node* f = qe.first; int sf = qe.second.first; int ss = qe.second.second; nodes[sf][ss].push_back(f->data); if(f->left) q.push({f->left, {sf-1, ss+1}}); if(f->right) q.push({f->right, {sf+1, ss+1}}); } vector ans; for(auto p : nodes) { for(auto it : p.second) { ans.insert(ans.end(), it.second.begin(), it.second.end()); } } return ans; }

[@ritikshandilya7075]

superb explanation

[@Gaurav-fb9ds]

vector < vector < int >> ans; for (auto p: nodes) { vector < int > col; for (auto q: p.second) { col.insert(col.end(), q.second.begin(), q.second.end()); } ans.push_back(col); } Can someone explain this?

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@utkarshsharma6650]

a bit difficult, but still understood :-/ will come back on it again

[@darshansurana7331]

In this video The time Complexity is (Addition of LogN)-> O((LogN + LogN + LogN) * N) and not (Multiplication of LogN)-> O((LogN * LogN * LogN) * N) first LogN for first map, second LogN for second map and third LogN for the multiset and this is done for all N elements so multiply by N. Am I Correct ?

[@Chirag_Sharma_]

This is the simplest possible code I can think of : class Solution { public: vector verticalTraversal(TreeNode* root) { vector ans; if (root == NULL) return ans; queue q; map mp; q.push({root, {0, 0}}); while (!q.empty()) { auto it = q.front(); q.pop(); TreeNode* node = it.first; int vertical = it.second.first; int level = it.second.second; mp[vertical][level].insert(node->val); if (node->left) q.push({node->left, {vertical-1, level+1}}); if (node->right) q.push({node->right, {vertical+1, level+1}}); } for (auto vertical : mp) { vector temp; for (auto level : vertical.second) { for (auto nodeVal : level.second) temp.push_back(nodeVal); } ans.push_back(temp); } return ans; } }; This would clearly explain how the last traversal works!

[@Ramu9119]

Nice Explanation

[@shubh13799]

Python3 Inorder Technique:- ``` def inOrder(node, i, j, res): if node is None: return inOrder(node.left, i - 1, j + 1, res) res[i].append((j, node.val)) inOrder(node.right, i + 1, j + 1, res) res = defaultdict(list) inOrder(root, 0, 0, res) return [[j[1] for j in sorted(res[i], key = lambda x: (x[0], x[1]))] for i in sorted(res)] ```

[@codeman3828]

Understood. Great video

[@PuneetMohanpuria]

this is much simpler implementation with same concept, this will work for vertical order, bottom view, top view verticalOrder(root,l,map){ if(root == null){ return; } if(map.get(l) != null){ List list = map.get(l); list.add(root.data); map.put(l,list); } else{ List list = new ArrayList(); list.add(root.data); map.put(l,list); } verticalOrder(root.left,l-1,map); verticalOrder(root.right,l+1,map); } public traverse(root){ HashMap map = new HashMap(); int l = 0; verticalOrder(root,l,map); //traverse this map }

[@shreyasharma7987]

What is the significance of storing the level? we can just use the vertical indexing to store the elements.

[@tusharnain6652]

Thank you STRIVER for this amazing series, and a little bit thanks to RELEVEL.

[@shaileshsingh6771]

Solution of this problem using preorder in cpp:- class Solution { private: void traversal(TreeNode* root, map &mp, int row, int col){ if(root == NULL) return; mp[col][row].insert(root->val); traversal(root->left,mp,row+1,col-1); traversal(root->right,mp,row+1,col+1); } public: vector verticalTraversal(TreeNode* root) { map mp; traversal(root,mp,0,0); vector res; for(auto i = mp.begin(); i != mp.end(); i++){ vector col; for(auto j=i->second.begin(); j != i->second.end(); j++){ for(auto k:j->second){ col.push_back(k); } } res.push_back(col); } return res; } };

[@nikharbehera5613]

we can also use map> nodes where nodes.first will represent vertical lines and multiset stores all the corresponding nodes (no need to keep track for level) am i right ??

[@XanderSR]

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.

[@111rhishishranjan2]

I was saying if let say we take down with -ve y axis of for node value 2 , we must store (2,-1,-1) .

[@shubhamagrawal22124]

Suggest you to keep meaningful variable names. Anyways thanks for all your content, really helpful.

[@UECAshutoshKumar]

Thank you sir

[@adamg2491]

Alternative solutions (similar to the one shown in the next video): vector verticalOrder(Node *root) { vector v{}; if(!root) return v; queue q{}; map m{}; q.push({root, 0}); while(!q.empty()) { auto qel = q.front(); q.pop(); Node* node = qel.first; int line = qel.second; if(m.find(line) == m.end()) { m.emplace(line, vector({node->data})); } else { m.at(line).push_back(node->data); } if(node->left) q.push(make_pair(node->left, line - 1)); if(node->right) q.push(make_pair(node->right, line + 1)); } for(auto& entry : m) { for(auto& data : entry.second) { v.push_back(data); } } return v; }

[@lavanyaprakashjampana933]

we love your content and we love you....🖤

[@amartyapatil4124]

@take U forward you need to make change in java tuple and code since we need to sort the priorityQueue based on y not based on x Here iscode with changes. class Tuple{ TreeNode node; int row; int col; public Tuple(TreeNode _node,int _row,int _col){ this.node=_node; this.col=_col; this.row=_row; } } class Solution { public List verticalTraversal(TreeNode root) { TreeMap map=new TreeMap(); List vertical=new ArrayList(); Queue q=new LinkedList(); q.offer(new Tuple(root,0,0)); while(!q.isEmpty()){ Tuple tuple=q.poll(); TreeNode node=tuple.node; int x=tuple.col; int y=tuple.row; if(!map.containsKey(x)){ map.put(x,new TreeMap()); } if(!map.get(x).containsKey(y)){ map.get(x).put(y,new PriorityQueue()); } map.get(x).get(y).add(node.val); if(node.left!=null){ q.offer(new Tuple(node.left,y+1,x-1)); } if(node.right!=null){ q.offer(new Tuple(node.right,y+1,x+1)); } } for(TreeMap ys:map.values()){ vertical.add(new ArrayList()); for(PriorityQueue nodes:ys.values()){ while(!nodes.isEmpty()){ vertical.get(vertical.size()-1).add(nodes.poll()); } } } return vertical; } }

[@tanaysingh5348]

thanks for such quality content

[@chiragsharma8905]

Simpler approach: Just store node's value, x and y in a list and custom sort it according to x, y and value. import java.util.*; class ValXY{ int val; int x; int y; ValXY(int val, int x, int y){ this.val = val; this.x = x; this.y = y; } } public class Solution { public static List verticalOrderTraversal(TreeNode root) { ArrayList list = new ArrayList(); fun(root, 0, 0, list); Collections.sort(list, new Comparator() { @Override public int compare(ValXY node1, ValXY node2) { if(node1.x!=node2.x){ return node1.x - node2.x; } if(node1.y!=node2.y){ return node1.y - node2.y; } return node1.val-node2.val; } }); int n = list.size(); List ans = new ArrayList(); for(int i=0; i

[@hetpatel7399]

Thank you:) Time complexity :O(n) +O(n)+O(nlogn) Space complexity:O(n)+O(n)+O(n)(stack space) Am I right???

[@chiragsharma8905]

@@hetpatel7399 yes.

[@chiragsharma8905]

@@hetpatel7399 you can also use a treemap btw

[@isheep9025]

instead of using multi set we can use simple vector and sort it according to vertical /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector verticalTraversal(TreeNode* root) { vector edges; queue q; q.push({{0,0},root}); while(!q.empty()) { int size=q.size(); for(int i=0;ival}); if(node->left) { q.push({{x-1,y+1},node->left}); } if(node->right) { q.push({{x+1,y+1},node->right}); } } } sort(edges.begin(),edges.end()); vector ans; vector temp; int vertical=1e9; for(auto ele:edges) { if(vertical!=ele.first.first) { if(temp.size()>0) ans.push_back(temp); temp.clear(); vertical=ele.first.first; temp.push_back(ele.second); } else temp.push_back(ele.second); } ans.push_back(temp); return ans; } };

[@namankeshari7332]

Thank you so much! This video is a life saver! Thanks again man!!