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.
@@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
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.
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;
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)
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.
@@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
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
@@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?!?
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, :)
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 = [];
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;
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.
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).
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
//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;
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; } };
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 ?
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.
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.
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 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; }
I have some confusion regarding the time complexity! My thoughts on time complexity are: One thing to note here is that the multiset for a vertical level V and horizontal level H will store at max 2 node values. This is because we know that at max there can be two guys with same vertical and horizontal level as the given tree is binary tree. So the complexity for maintaining the multiset can be ignored. Now, what about the vertical and horizontal level? At max the vertical level i.e. the max width of the binary tree in the worst case can be 2^H - 2^(H-1) which can be considered as 2 ^ H in the case of perfect binary tree, and the max value of horizontal level would be the height of the tree which is H. Now we know the max values for vertical and horizontal levels. To maintain the map of vertical levels we require log(2 ^ H) (base 2) time and to maintain the inner map of horizontal levels we require log(H) time. So, in total the time complexity would be O(N * H * log(H)) where N is for the traversal of the tree. P.S: Please correct me if I'm wrong
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;
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); }
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!
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 }
yes comparator can do that but ig when you sort it using comparator in worst case time complexity is still in O(nlogn) and above method do it in O(n) i think.. BTW code for comparator in GFG question it worked: typedef pair pr; // hi, l, lo, data // hi=> horizontal index, l=>level of node, level order number class Solution { public: //Function to find the vertical order traversal of Binary Tree. // time complexity will be O(nlogn) not O(n) void pre(Node* root, int hi, int l, vector &ans, int &lo){ if(root==NULL) return; ans.push_back({{hi,l},{root->data,lo++}}); pre(root->left, hi-1, l+1, ans, lo); pre(root->right, hi+1, l+1, ans, lo); } static bool comp(pr p1, pr p2){ if(p1.first.firstp2.first.first) return false; if(p1.first.secondp2.first.second) return false; if(p1.second.second
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.
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
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
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..
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.
I'm enrolled in Coding Ninjas Competitive Programming Premium course. Your content has much more depth than CN.
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
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.
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
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.
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.
thanks man
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;
}
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
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;
}
@@atulwadhwa192 For each vertical level, your vector should be filled from top to bottom, this thing will not happen with this code
4:37 There is a small typo, the co-ordinates of the rightmost node is actually (2, 2) not (1, 2)
you are correct..
nah striver is just testing us if we are paying attention
@@dom47 "not a bug, but a feature" type comment 😂
i think this is the hardest question of this playlist till now...... it really required like 1 day to understand this and code it.
Thank you so much for explaining the C+++ code..after lot of searching I found this video and it's awesome
now I know why some said donot use java for cp ,c++ is a life saver
Understood! Such an amazing explanation as always, thank you very much!!
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
absolutely amazing explanation, learned a lot more than tree traversal in this video (my STL is not the best)
same brother
Brilliant explanation and hats off to whoever though of this solution.
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)
Or unordered map and queue
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 .
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.
you make leetcode hard problems easy to understand!!!! tysm
Thank you Striver Bhaiya. You're a inspiration to me.
Got the whole approach...but struggling with the last part, which is traversing the priority queue and adding into arraylist.
i've done it myself by using bfs(level order) and preorder..(dfs, and used tuple to store all values.. like vector vec; )
Good question. Its mostly about visualizing how the node data is stored in the root map.
understood.................thanks bhaiya for the amazing videos
Understood. Great video
Solved myself without watching the solution using map of map. got a dopamine hit. Thanks striver.
Thank you so much! This video is a life saver! Thanks again man!!
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
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 ?
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
Why time complexity is O(N*logn)? we are using map > So it should be O(N*logN*logN*logN). please explain.
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)??
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;
}
};
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?!?
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, :)
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.
Great explaination!❤️
Waiting for BSTs... 😌
We can also use map
Thank you STRIVER for this amazing series, and a little bit thanks to RELEVEL.
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;
}
};
Nice Explanation
i did the 90% question myself i just couldnot find out which datastructure to use i am super happy about it ..................
Understooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooood, Ctr + right arrow, for shifting the chapter of ads in video
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;
Lovely explanation yaar itne pyaar se kisi ne nhi sikhaaya
tough but it was very great explanation
superb explanation
what an easy clarification yar man
Could we have just used "mapint>> nodes"?
it's not allowed because std::map keys must be of a type that supports comparison for equality and ordering.
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.
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).
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;
}
NICE SUPER EXCELLENT MOTIVATED
This approach takes O(n*logn) time complexity. Can you please make a video on efficient solution that takes O(n)?
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
Completed 22/54(40% done) !!!
What a great explanation 🙏🙏🙏🙏🙏
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
Yeah I think then we just need to use
map
What is order of overlapping ?
//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;
}
};
Understood ❤❤
Tip:
You should have taken 'y' as vertical and 'x' as level. Then it will be more easy to visualise in the coordinate system.
Bro, trace the given code completely and you'll find his method as the most appropriate.
visualize this as x and y coordinate
@@debasmitamallick6489 yes correct.
vertical lines are made on x-axis buddy. Consider them as axes as told by @debasmita
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;
}
};
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 ?
Thank you Bhaiya
Suggest you to keep meaningful variable names. Anyways thanks for all your content, really helpful.
thanks alot!
What is the significance of storing the level? we can just use the vertical indexing to store the elements.
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?
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.
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.
Extremely easy explanation for a leetcode hard level question!
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 ??
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.
Thank you very much. You are a genius.
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;
}
Great explaination🤩
I have some confusion regarding the time complexity!
My thoughts on time complexity are:
One thing to note here is that the multiset for a vertical level V and horizontal level H will store at max 2 node values. This is because we know that at max there can be two guys with same vertical and horizontal level as the given tree is binary tree. So the complexity for maintaining the multiset can be ignored.
Now, what about the vertical and horizontal level? At max the vertical level i.e. the max width of the binary tree in the worst case can be 2^H - 2^(H-1) which can be considered as 2 ^ H in the case of perfect binary tree, and the max value of horizontal level would be the height of the tree which is H.
Now we know the max values for vertical and horizontal levels. To maintain the map of vertical levels we require log(2 ^ H) (base 2) time and to maintain the inner map of horizontal levels we require log(H) time.
So, in total the time complexity would be O(N * H * log(H)) where N is for the traversal of the tree.
P.S: Please correct me if I'm wrong
bhai 2 se jada values bhi ho skti hai ek vertical pe
Legend ❤🔥
understood!
Awesome Explanation Bhaiya
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]
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;
I was saying if let say we take down with -ve y axis of for node value 2 , we must store (2,-1,-1) .
I think, at node 10, it should be (2,2) instead of (1,2).
Smjh le n yrr
@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;
}
}
a bit difficult, but still understood :-/ will come back on it again
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);
}
class Solution {
public:
void dfs(TreeNode* root,int wide,int level,map& mp)
{
mp[wide][level].insert(root->val);
if(root->left)
dfs(root->left,wide-1,level+1,mp);
if(root->right)
dfs(root->right,wide+1,level+1,mp);
}
vector verticalTraversal(TreeNode* root) {
map mp;
vector ans;
if(root==nullptr)
return ans;
int level=0;
int wide=0;
dfs(root,wide,level,mp);
for(auto x: mp)
{
vector temp;
for(auto i:x.second)
for(auto y: i.second)
temp.push_back(y);
ans.push_back(temp);
}
return ans;
}
};
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);
}
}
Huge respect...❤👏
we love your content and we love you....🖤
which data structure will be used to store the node.value,y,x in python language?
Just check once that in line 12, it should be nodes[y][x]
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!
thanks for such quality content
Doubt : In the last part
//This is correct
for(auto it:mp){ //vertical
vector col;
for(auto i:it.second) //level
col.insert(col.end(), i.second.begin(), i.second.end());
ans.push_back(col);
}
//But why not this....why cant I use push_back in vector instead of " col.insert(col.end()...) " ???
for(auto it:mp){ //vertical
vector col;
for(auto i:it.second) //level
col.push_back( i.second.begin(), i.second.end());
ans.push_back(col);
}
col is having data type as int and not that of any 1d vector or set, we cannot pushback
In GFG they are taking map instead of map. Can u please tell me why and whats the difference??
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
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
}
I think a good vector comparator function will do all the map thing
yes comparator can do that but ig when you sort it using comparator in worst case time complexity is still in O(nlogn) and above method do it in O(n) i think..
BTW code for comparator in GFG question it worked:
typedef pair pr; // hi, l, lo, data
// hi=> horizontal index, l=>level of node, level order number
class Solution
{
public:
//Function to find the vertical order traversal of Binary Tree.
// time complexity will be O(nlogn) not O(n)
void pre(Node* root, int hi, int l, vector &ans, int &lo){
if(root==NULL) return;
ans.push_back({{hi,l},{root->data,lo++}});
pre(root->left, hi-1, l+1, ans, lo);
pre(root->right, hi+1, l+1, ans, lo);
}
static bool comp(pr p1, pr p2){
if(p1.first.firstp2.first.first) return false;
if(p1.first.secondp2.first.second) return false;
if(p1.second.second
can we solve this qs without level and just by using vertical, node ?
You make advance problems seem average, Thanks!!
Understood
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.
understood
i think no need to maintain level of each node.