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.
@@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
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..
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.
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.
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; }
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
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)
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
@@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
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.
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;
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 ?
@@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?!?
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; }
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.
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.
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.
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, :)
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; } };
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).
In c++ code line no. 26 , how are we making sure that when two or more complete multiset items are inserted in a column , the column will have sorted elements? Multisets contain sorted elements but when two or more multiset contents are pushed into a vector one after the other, the resulting vector might not be sorted.
my saved notes are not showing in atoz sheet. And on opening it from saved notes on website , the notes are not correctly placed like how i had originally wrote it and some content from it is also missing . If Anyone knows how to fix it please help.
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
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); }
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]
@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; } }
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 ??
if(node->left) q.push({node->left,{x-1,y+1}}); While pushing the updated position of vertical and level in the queue I am using x-- and y++ in the place of x-1 and y+1(for both left and right node). But It is giving me the wrong answer. Can somebody help me out.
I am not able to unserstand one thing that how section in code is working:_ col.insert(col.end(), q.second.begin(), q.second.end()); ``` vector ans; for(auto p: nodes){ vector col; for(auto q: p.second){ // Insert node values // into the column vector col.insert(col.end(), q.second.begin(), q.second.end()); } // Add the column vector // to the final result ans.push_back(col); } return ans; ```
