Vertical order traversal of a binary tree | Leetcode
This video explains how to find the vertical order traversal of a binary tree which is from Leetcode 987.This problem is slightly different from the easier version where we are just required to find vertical order traversal based on Y-axis only.In this problem, we are required to find vertical order traversal of a binary tree based on X and Y axis.We can solve it using DFS as well as BFS.I have explained in detail the DFS approach but simple DFS/Recursion won't work which i have shown using an example.I have the data structure which will be used to solve it with reason.We can use Map of Map of Set in order to maintain the constraints of the problem statement.I have explained the entire algorithm to find vertical level order traversal using example.At the end of the video, i have explained the CODE walk through.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
Пікірлер: 121
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!
@techdose4u
3 жыл бұрын
👍
@neversettlejay
2 жыл бұрын
wait set doesn't handle duplicate values means!!!!? Set is meant to take just unique values right?
@dineshsaini6051
2 жыл бұрын
@@neversettlejay yes, hence you'll end up missing duplicate values.
@pranavsharma7479
2 жыл бұрын
use multiset
@commentator2407
Жыл бұрын
@@neversettlejay ya
Your teaching style is rock solid thanks for this wonderful explanation of the topic I stumbled upon.
@techdose4u
2 жыл бұрын
Thanks 👍🏼
I was getting runtime Error, but you solved my doubt. Thanks a lot for your Awesome Explanation!!
@techdose4u
3 жыл бұрын
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
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?
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.
Please keep this series on going and free of cost. Please
@techdose4u
3 жыл бұрын
😳
Ye tech ki dose bahut imp h.Ye sab coders ko leni chaiye.....
Can someone tell why "ans.push_back(vector())" is used in 1st approach);
can you let me know why we have inserting value on basis of col * row and not in row * col.
thank you sir , your lectures help very much I just watched little of it and understood what to do next, thank you
@techdose4u
3 жыл бұрын
Nice :)
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.
great explanation, ans.push_back(vector()) , I dont understand what is these and why we use "vector()" ? Would you please explain me
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!!!
@techdose4u
3 жыл бұрын
Welcome
Seriously very amazing solutions of this problem you provide 😊.. thanking you so much sir
@techdose4u
4 жыл бұрын
Welcome :)
Thank you so much! I was stuck at this question.. you made it clear.
@techdose4u
4 жыл бұрын
Welcome :)
wonderful explanation, solved this leetcode problem in one go just by following your explanation .
@techdose4u
2 жыл бұрын
Great ❤️
best explaination for this problem and dfs is easier than bfs in this tbh
finally understood the problem lots of the Thank you!!❤❤
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
what is the time complexity of this code?
The content of this channel is growing exponentially surely this will become a repository to crack faang interviews thanks for your effort tech dose
@techdose4u
4 жыл бұрын
Thanks for your appreciation. I hope it helps every student preparing for programming interviews.
Too good explaination.This video is really good and all contents are easily understable .
@techdose4u
2 жыл бұрын
Thanks 😊
bhaiya explanation is awsm
Nicely explained🙌..keep up with this awesome work.👍
@techdose4u
4 жыл бұрын
Thanks
For duplicate values in Python simply use List and make sorting arrangements accordingly (DFS approach)
Which will run faster BFS or DFS?
How to print top view of bi art tree in o(n)
I was not able to solve the problem due to 1st constraint, thank you for the solution.
@techdose4u
4 жыл бұрын
Thanks :)
can we solve it recursively??
Awesome solution dude. Hats off to you.
@techdose4u
4 жыл бұрын
Thanks :)
What should be the space complexity?
Brilliant approach.
@techdose4u
4 жыл бұрын
Thanks :)
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?
@ratankumar1399
2 жыл бұрын
But it is assumed that there is no duplicates in Tree,if there is duplicates then go for multiset
@harshbokan6874
2 жыл бұрын
Use multiset
Huge thanks💜
@techdose4u
2 жыл бұрын
Welcome 😀
Instead of using set using multiset will solve the problem of having duplicates in same row and col.
Really good explanation !
@techdose4u
3 жыл бұрын
Thanks :)
Hello, Could you please help how to solve this question using JavaScript? Because map and set are little different in JS.
@techdose4u
3 жыл бұрын
I will ask people to share their code in comment in different languages. It will be much more helpful.
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?
@techdose4u
2 жыл бұрын
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.
@JohnWick-kh7ow
2 жыл бұрын
@@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)
Better than striver! But you could have used unordered map and mutilset instead of map and set.
Nice explanation!
@techdose4u
3 жыл бұрын
Thanks :)
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.
@techdose4u
4 жыл бұрын
Its difficult to accomodate with graph videos as many of them are pending as well. So, I will try after graph.
@sakthim7160
4 жыл бұрын
@@techdose4u thank you!
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
Thank you so much
@techdose4u
3 жыл бұрын
Welcome :)
Excellent explanation sir
@techdose4u
2 жыл бұрын
Thanks 😃
awesome explanation
@techdose4u
3 жыл бұрын
Welcome :)
Thay asked the same today in my interview Lucky me I watched this video after the interview Thank you youtube Ur recommendation algo sucks!
@techdose4u
3 жыл бұрын
How does youtube know that you want to see this 😂 Google knows about your interview too!!
@vijayjayaram606
3 жыл бұрын
@@techdose4u scary. My meeting invite 😱
@techdose4u
3 жыл бұрын
@@vijayjayaram606 Haha :P
That was epic explanation!
@techdose4u
3 жыл бұрын
Thanks :)
how were we supposed to figure this out on ur own without looking at the solution?
good problem
where you work Google or Meta?
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.
@praveenprakash6336
4 жыл бұрын
For students from tier 3 college.
@techdose4u
4 жыл бұрын
I will try to make it.
@praveenprakash6336
4 жыл бұрын
@@techdose4u we will be waiting ..
@depression_plusplus6120
3 жыл бұрын
@@praveenprakash6336 forget bro...we NITS IITANS deserve them..you go for TCS🤣
@praveenprakash6336
3 жыл бұрын
@@depression_plusplus6120 Don't judge a guy by his college okay.....
BRILLIANT
@techdose4u
3 жыл бұрын
😀
Thanks sir
@techdose4u
4 жыл бұрын
Welcome :)
what is the difficulty level of this one
@techdose4u
3 жыл бұрын
Medium I think
Code link is not reachable..
@techdose4u
3 жыл бұрын
I will check
Approach = 🤘
@techdose4u
3 жыл бұрын
🤘🏼
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
Saviour!!
@techdose4u
3 жыл бұрын
:)
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
TreeMap
Hard to understand
@techdose4u
3 жыл бұрын
Please watch it again
@sase1017
3 жыл бұрын
@@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 !
@techdose4u
3 жыл бұрын
Thanks :)