Code in Python for DFS(It becomes helpful with sorted function): class Solution: def helper(self, placement,level, root, dic): if(not root): return dic[placement].append((level, root.val)) self.helper(placement-1, level+1, root.left, dic) self.helper(placement+1, level+1, root.right, dic)
def verticalTraversal(self, root: TreeNode) -> List[List[int]]: dic = defaultdict(list) self.helper(0,0, root, dic) result = [] for i in sorted(dic.keys()): temp = [] for j in sorted(dic[i]): temp.append(j[1]) result.append(temp) return result
what does iterating over m1.second and m2.second actually mean? Is m2.second having the values of the tree in the ascending order? And we are pushing a vector() into the ans 2d vector, is it just to create some space in the answer vector?
Nice explanation. One finding though, Set will remove duplicates. For example if we have same values for given (x, y) coordinates, we will endup missing one value in output. Am I missing something?
everything is good but you have named the coordinates of node values wrong, provided the root is the origin (0,0). Go to timestamp 12:43 for your reference.
In the Map Map Set, if you use Unordered_map then time will be NlogN in total. If you use Map then NlogNlogNLogN. 2 extra logs for ordered map key search. So. It depends on your choice of DS.
Will you able to make videos on binary lifting? Which will be very helpful to solve problems like lowest common ancestor of given two nodes and kth ancestors of a given node in a tree.
This problem can be solved using HashMap & PriorityQueue in Java. `class Solution { public List verticalTraversal(TreeNode root) { Map map = new HashMap(); int[] width = {0, 0}; verticalTraversal(root, 0, 0, map, width); List result = new ArrayList(); for (int i = width[0]; i
The solution is really good, but I would like to point out that using set doesn't handle duplicate values. So to pass all the cases use multiset!
👍
wait set doesn't handle duplicate values means!!!!? Set is meant to take just unique values right?
@@neversettlejay yes, hence you'll end up missing duplicate values.
use multiset
@@neversettlejay ya
Please keep this series on going and free of cost. Please
😳
Your teaching style is rock solid thanks for this wonderful explanation of the topic I stumbled upon.
Thanks 👍🏼
Ye tech ki dose bahut imp h.Ye sab coders ko leni chaiye.....
Solved it one try within 20 mins using treemap of treemap of priorityQueue. I must say I learned well from you lol. Thank you so much legend!!!
Welcome
wonderful explanation, solved this leetcode problem in one go just by following your explanation .
Great ❤️
I was getting runtime Error, but you solved my doubt. Thanks a lot for your Awesome Explanation!!
Welcome :)
Your intuition to explain is so good , and I have a doubt on for loop.... Would you please explain how the for loop work.?
It really helpful to me
best explaination for this problem and dfs is easier than bfs in this tbh
The content of this channel is growing exponentially surely this will become a repository to crack faang interviews thanks for your effort tech dose
Thanks for your appreciation. I hope it helps every student preparing for programming interviews.
Better than striver! But you could have used unordered map and mutilset instead of map and set.
thank you sir , your lectures help very much I just watched little of it and understood what to do next, thank you
Nice :)
I was not able to solve the problem due to 1st constraint, thank you for the solution.
Thanks :)
Too good explaination.This video is really good and all contents are easily understable .
Thanks 😊
great explanation, ans.push_back(vector()) , I dont understand what is these and why we use "vector()" ? Would you please explain me
Seriously very amazing solutions of this problem you provide 😊.. thanking you so much sir
Welcome :)
Awesome solution dude. Hats off to you.
Thanks :)
finally understood the problem lots of the Thank you!!❤❤
Instead of using set using multiset will solve the problem of having duplicates in same row and col.
Thay asked the same today in my interview
Lucky me
I watched this video after the interview
Thank you youtube
Ur recommendation algo sucks!
How does youtube know that you want to see this 😂 Google knows about your interview too!!
@@techdose4u scary. My meeting invite 😱
@@vijayjayaram606 Haha :P
Code in Python for DFS(It becomes helpful with sorted function):
class Solution:
def helper(self, placement,level, root, dic):
if(not root):
return
dic[placement].append((level, root.val))
self.helper(placement-1, level+1, root.left, dic)
self.helper(placement+1, level+1, root.right, dic)
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
dic = defaultdict(list)
self.helper(0,0, root, dic)
result = []
for i in sorted(dic.keys()):
temp = []
for j in sorted(dic[i]):
temp.append(j[1])
result.append(temp)
return result
what does iterating over m1.second and m2.second actually mean? Is m2.second having the values of the tree in the ascending order? And we are pushing a vector() into the ans 2d vector, is it just to create some space in the answer vector?
Brilliant approach.
Thanks :)
For duplicate values in Python simply use List and make sorting arrangements accordingly (DFS approach)
Nice explanation. One finding though, Set will remove duplicates. For example if we have same values for given (x, y) coordinates, we will endup missing one value in output. Am I missing something?
But it is assumed that there is no duplicates in Tree,if there is duplicates then go for multiset
Use multiset
Inside the first for loop, the first statement of pushing the vector() means are we pushing the entire vector?? I am confused with the representation.
Thank you so much! I was stuck at this question.. you made it clear.
Welcome :)
bhaiya explanation is awsm
Can someone tell why "ans.push_back(vector())" is used in 1st approach);
Nicely explained🙌..keep up with this awesome work.👍
Thanks
Huge thanks💜
Welcome 😀
Really good explanation !
Thanks :)
awesome explanation
Welcome :)
Excellent explanation sir
Thanks 😃
everything is good but you have named the coordinates of node values wrong, provided the root is the origin (0,0). Go to timestamp 12:43 for your reference.
i don't think we have similar DS in nodeJS, map and set both follow insertion order here, so we manually need to sort the keys/values.
Bro your explanation is truly good. Bro could you please make a video for 1st year students in order to get into product based companies.
For students from tier 3 college.
I will try to make it.
@@techdose4u we will be waiting
..
@@praveenprakash6336 forget bro...we NITS IITANS deserve them..you go for TCS🤣
@@depression_plusplus6120 Don't judge a guy by his college okay.....
can you let me know why we have inserting value on basis of col * row and not in row * col.
Striver said that the time complexity is O(N*logN). You are saying that time complexity is O(N*logN*logN*logN). Which one is right?
In the Map Map Set, if you use Unordered_map then time will be NlogN in total. If you use Map then NlogNlogNLogN. 2 extra logs for ordered map key search. So. It depends on your choice of DS.
@@techdose4u I asked him he agreed that time complexity will be O(N*LogN*LogN*LogN). He told the time complexity of java code which is O(N*logN)
Will you able to make videos on binary lifting? Which will be very helpful to solve problems like lowest common ancestor of given two nodes and kth ancestors of a given node in a tree.
Its difficult to accomodate with graph videos as many of them are pending as well. So, I will try after graph.
@@techdose4u thank you!
Nice explanation!
Thanks :)
Thank you so much
Welcome :)
BRILLIANT
😀
That was epic explanation!
Thanks :)
Hello,
Could you please help how to solve this question using JavaScript?
Because map and set are little different in JS.
I will ask people to share their code in comment in different languages. It will be much more helpful.
This problem can be solved using HashMap & PriorityQueue in Java.
`class Solution {
public List verticalTraversal(TreeNode root) {
Map map = new HashMap();
int[] width = {0, 0};
verticalTraversal(root, 0, 0, map, width);
List result = new ArrayList();
for (int i = width[0]; i
Which will run faster BFS or DFS?
Approach = 🤘
🤘🏼
What should be the space complexity?
what is the time complexity of this code?
good problem
but if we have duplicates elements in same row and column and set will not work it would be better to use vector instead of set
Thanks sir
Welcome :)
How to print top view of bi art tree in o(n)
can we solve it recursively??
how were we supposed to figure this out on ur own without looking at the solution?
Not working for test case->
[1,2,3,4,5,6,null,null,7,8,null,null,9,null,10,null,11,10],hence instead of set I took vector in map
Saviour!!
:)
where you work Google or Meta?
what is the difficulty level of this one
Medium I think
Code link is not reachable..
I will check
TreeMap
Hard to understand
Please watch it again
@@techdose4u Thank you so much, I understand pretty well and be able to code out by myself now, your visualization and explanation helped tremendously
Nice explanation !
Thanks :)