Table of Contents: The Problem Introduction 0:00 - 1:10 Going Through The Levels 1:10 - 3:00 A Traumatic Flashback 3:00 - 3:29 We Realize We Already Know How to Do This 3:29 - 3:56 But...We Have A Problem 3:56 - 5:52 A Hashtable Might Be Able To Help Us 5:52 - 7:14 The Breadth First Search Walkthrough 7:14 - 13:24 Time Complexity 13:24 - 13:29 The Show Gets Hijacked By Ishan 13:29 - 13:51 A Special Property of Trees 13:51 - 14:03 An Example of The Property 14:03 - 14:41 Space Complexity 14:41 - 14:55 The Show Is Reclaimed 14:55 - 15:08 Wrap Up: Subscribe & Validate My Existence 15:08 - 15:35 Sort of Mistakes: 5:57 -> O(1) does not mean immediate access. It is an asymptotic bound on how runtime scales with large input sizes. 10:19 -> Many times I referenced the "seen" HashSet as a hashtable. I just mean it is a set of items with unique signatures. White Noise / Hissing On Audio: I know about it. I am still working to get the right sound settings right on my mic to make this disappear. The code for this problem is in the description. Fully commented for teaching purposes.
I love how you explained things in the video, it was really easy to follow start to finish! The only complaint I have is the code isn't in the description like you said it would be.
I love the way you explain this problem. I have solved this problem in the past but every time I struggle to traverse the parent nodes of start element. The way you add Hashmap to traverse the root is amazing. I dont think that I will forget this method now. Thanks for sharing this.
Your explanations are the clearest I have ever seen. I've been spending hours on this problem, then I understand the solution within 15 minutes by watching this. I appreciate you uploaded all these great explanations. I love them, I mean all of them.
Seeing that you have a Video on a Question that I'm Stuck on........gives me hope that I'll ever get stuck on this Type of Question Again.......Thanks Man....I Can't thank you enough......you've itched some questions and concepts into my Brain.
I kinda had doubts as to whether this will work with different nodes having the same value. And then I saw the code and realized you were storing the node references instead of the actual values. Thanks!
This man is saving lives out here . I am subbed and hooked .. please keep uploading .. love your work and approach to problem solving and getting that across to people in a way that feels 'for a lack of a better word. Personal .
A perfect stop to every tricky problem, Thanks a ton! But is this the right choice to watch a video for a new topic? Basically, how do you suggest to watch your videos?
Firstly, thank you for your work. You are definitely the best on youtube doing these walkthroughs and a huge help to many. Second, could you also iterate through the tree and construct a new graph (list of edges), and then do a regular graph bfs to k distance? Although its an extra step it is still the same time complexity, so it is a trade off for a little more simplicity?
"Could you also iterate through the tree and construct a new graph (list of edges), and then do a regular graph bfs to k distance?" yes "Although its an extra step it is still the same time complexity, so it is a trade off for a little more simplicity?" Yes, still O(|V|+|E|) as it is BFS. And also O(|V|) space. Just the "real" space usage will be more if we clone the whole graph.
Benyam had to join the SWE website cause the content is amazing...BUT REAL TALK in an interview where you spent 20-30 minutes on behavioral, it would be pretty wild to get this!!! 1 main function with 3 helpers approx 80+ lines of code (for us java peeps ) , 'i cry everytim'
Thank you so much for explaining with such clarity and articulation so that even a newbie like myself can understand how to go about solving these types of problems!
Hi Ben, thanks for another fantastic video. Just wondering if you take any requests for specific problems? Recently, I was stuck on the “Median of two sorted arrays” problem and none of the tutorials were any helpful. I also heard it’s quite a popular question. I know you probably already have an agenda in mind but it’d great if you can cover that. Thanks again for these tutorials!
hahaha yes. Thank you for asking so kindly. Yes that is a question on the very top of my mind. I am very aware of it and want to cover it but have no idea when it will happen. So much ground to cover.
@@raksstrife1233 Yeah. I mean...this is all about making resources available and I'd be amiss if I didn't acknowledge his channel since it is huge. But I want to do it better than him of course.
Like your explanations because you focus on the intuition and approach behind reaching the solution. Also, you repeat important keywords quite a bit which is helpful in understanding a difficult/new approach. Keep up with the good work :)
This is very complicated explanation of the problem. To be honest I really did not understand until I manage to solve by myself. This is for those who does not understand properly from this video. 1 : define a vector which called 'result' to hold result nodes 2 : convert the given binary tree into un-directed graph. 3 : use the 'start' node as a starting vertex for breadth-first search 4 : during breadth-first search check the distance of the nodes, if their distance is equal to K push into result vector. 5 : return the result vector.
This is a great video. Very clear and easy to understand explanation. Why don't you make a playlist where you organize your videos in order(e.g. 1st video to watch and so on) for people to follow?
people have suggested this but....1.) I can't make anymore playlists...I've hit the cap....and 2.) I don't think there is any order...it is just whatever topic you are weak at...and you practice that....I think that's the optimal strategy....there can be no master order of questions because that ignores that everyone is generally different and more or less adept at different categories to different degrees
Hi, I still don't see how you have been able to include parent 3 from start root node 5. Shouldn't we have to start traversing the "graph" from the root 3 before so we can know that 3 is indeed a parent of 5? I feel like before you started implementing the solution, it was going to be a 2 step process: - 1st traverse the tree to have the desired mapping - 2nd graph traversal now that we can go upwards. But then, you have just started right away at 5 with the capability of going upwards. Where did I loose you? Thanks! Awesome content : )
Hey, I don't remember the example in detail as I did this nearly a year ago. Could you condense the question or give me timestamps? I am rapidly responding to youtube comments
@@BackToBackSWE : when you started adding the nodes in the hashmap, You started directly from node 5 (at 9:22 ). How did you reach node 5 directly ??.... Secondly , i am assuming that you first wrote, the code to recursively reach node 5 , but if thats the case then how will you know whose the parent of the node 5 once you have already reach node 5 ??... . I understand the point that we are treating it as an undirected graph but it still technically is a Tree which is directed in nature. I hope i am able to cleary state the problem??
yes same problem. Can you explain how to traverse through the tree from the node to create a hash table that allows any node to access their parents? Essentially the code behind how you make it bidirectional
Thank you dude. First, i thought i should use hashmap for storing distance of nodes from the target node but ur tricked help to map parenting of node that help me
Good explanation but would help if the parent hash table was visualized here too. Was a bit confused due to the lack of that reference. I only say that because the rest of the explanation was crystal clear haha
Hi, I love your videos, they're very clear! May I offer a suggestion though? Please don't put hints to the solution in the title, it spoils it when people are trying to solve it. Thanks!
Thank you so much for this nice explanation. I should have subscribed your channel earlier. I'm having an Amazon interview next week but I feel that I'm not prepared yet.
Thanks very much for the awesome videos and detailed explanations. Really loved the series. Wanted to ask if you can also make a video to explain the method using DFS to solve this problem? Thanks!
Actually, you can save some more space. Instead of using a "seen" HashSet, you can simply remove any node you already put in the queue from the "parent" map. That way, if you try to add a node to the queue, whether it's a parent, left or right - if it isn't in the map, you simply don't add it, since you already "visited" it. This solution will not only remove the duplicate space, but actually reduce the space as you go on.
Bro, this is crazy, I've watched a handful of your videos and swore I recognized some of the classrooms you've been in. Then realized we both are from the same school lol. Class of '18 and your videos are great refreshers for studying to get my next job. Keep up the good work and go terps 🐢
Just to clear things out: 'bidirectional' here means the children and parent of a node, unlike the more common usage where two simultaneous traversals occur (one from node u, and the other from node v).
Table of Contents:
The Problem Introduction 0:00 - 1:10
Going Through The Levels 1:10 - 3:00
A Traumatic Flashback 3:00 - 3:29
We Realize We Already Know How to Do This 3:29 - 3:56
But...We Have A Problem 3:56 - 5:52
A Hashtable Might Be Able To Help Us 5:52 - 7:14
The Breadth First Search Walkthrough 7:14 - 13:24
Time Complexity 13:24 - 13:29
The Show Gets Hijacked By Ishan 13:29 - 13:51
A Special Property of Trees 13:51 - 14:03
An Example of The Property 14:03 - 14:41
Space Complexity 14:41 - 14:55
The Show Is Reclaimed 14:55 - 15:08
Wrap Up: Subscribe & Validate My Existence 15:08 - 15:35
Sort of Mistakes:
5:57 -> O(1) does not mean immediate access. It is an asymptotic bound on how runtime scales with large input sizes.
10:19 -> Many times I referenced the "seen" HashSet as a hashtable. I just mean it is a set of items with unique signatures.
White Noise / Hissing On Audio:
I know about it. I am still working to get the right sound settings right on my mic to make this disappear.
The code for this problem is in the description. Fully commented for teaching purposes.
please make more videos
thanks a lot
ok
I cannot see the code for the problem
the code isn't in the description?
I love how you explained things in the video, it was really easy to follow start to finish! The only complaint I have is the code isn't in the description like you said it would be.
Yo that man Ishan hella smooth
yeah
@@BackToBackSWE for real
@@Travis-ko2jo !!!
You are the best tutor on youtube for dsa. Please make more and more videos to help us !!! Thanks a lot
ok
I never see your code, you explain the algo and I try to code it myself. Thanks for the great explanation
I love the way you explain this problem. I have solved this problem in the past but every time I struggle to traverse the parent nodes of start element. The way you add Hashmap to traverse the root is amazing. I dont think that I will forget this method now. Thanks for sharing this.
nice
Hey! I really do appreciate your videos. It makes everything super clear! You’re one of the best teachers so far. Keep being hyped!!
From South Korea
nice!! thanks for commenting
I am a beginner in DS and algorithm. Have gone through 3 other channels. But I would say this is the best. Very brilliant way of conveying. Thank you
thanks
Your explanations are the clearest I have ever seen. I've been spending hours on this problem, then I understand the solution within 15 minutes by watching this. I appreciate you uploaded all these great explanations. I love them, I mean all of them.
Aw thanks haha, dang, the first videos suck
Seeing that you have a Video on a Question that I'm Stuck on........gives me hope that I'll ever get stuck on this Type of Question Again.......Thanks Man....I Can't thank you enough......you've itched some questions and concepts into my Brain.
You literally put lot of effort to make us understand. Appreciate it a lot.
sure
I kinda had doubts as to whether this will work with different nodes having the same value. And then I saw the code and realized you were storing the node references instead of the actual values. Thanks!
Ah yeah, memory addresses have to to be unique.
really helpful this video, the clearest explanation in UA-cam, thank you so much
sure
How can your content be so good man? Video after video. The best. Take a bow.
This man is saving lives out here . I am subbed and hooked .. please keep uploading .. love your work and approach to problem solving and getting that across to people in a way that feels 'for a lack of a better word. Personal .
great to hear and thx
Only a word can describe you as a whole....... and that word is AMAZING
thx
A perfect stop to every tricky problem, Thanks a ton!
But is this the right choice to watch a video for a new topic?
Basically, how do you suggest to watch your videos?
We are releasing a new platform to keep everything organized today
You are brilliant, having a great gift of presenting, and also your video editing and timing is great (cutting out the right stuff). Subscribing!
thanks haha
Firstly, thank you for your work. You are definitely the best on youtube doing these walkthroughs and a huge help to many.
Second, could you also iterate through the tree and construct a new graph (list of edges), and then do a regular graph bfs to k distance? Although its an extra step it is still the same time complexity, so it is a trade off for a little more simplicity?
"Could you also iterate through the tree and construct a new graph (list of edges), and then do a regular graph bfs to k distance?"
yes
"Although its an extra step it is still the same time complexity, so it is a trade off for a little more simplicity?"
Yes, still O(|V|+|E|) as it is BFS. And also O(|V|) space. Just the "real" space usage will be more if we clone the whole graph.
But that's not the question bro
All the video was super cool to watch, but the humor again... stole the show!(at the end)
Great Job!
thanks
Such a Clear explanation of the thought process and the solution ! Great one as-usual
thanks
Love the way you start with your thought process, brilliant. Keep up the hard work
thanks, will do
Was stuck in this qsn for almost a day . Thanks dude!
sure
Amazing Explanation, thanks Benyam!!!
hey thanks
Nice one. I like the simplicity and explanation. Thanks for that!
sure
Was able to solve this problem on my own after listening to your great explanation. Thanks!
sweet
Such an ingenious approach ! Hats off to you mate. Keep posting :)
thanks
Thank you so much for the video. Crisp and clear. No bullshit. Love videos like these!! Keep up the good work!!
thanks
This is the beast channel I ever seen.THKS you and your team make the toppest resources available for us.
ye
Benyam had to join the SWE website cause the content is amazing...BUT REAL TALK in an interview where you spent 20-30 minutes on behavioral, it would be pretty wild to get this!!! 1 main function with 3 helpers approx 80+ lines of code (for us java peeps ) , 'i cry everytim'
You explanations are simple and easy to follow
Thank you so much for explaining with such clarity and articulation so that even a newbie like myself can understand how to go about solving these types of problems!
This guy is so much clear in his thought process
This guy agrees :) haha
Great walkthrough! Loving these videos.
sure
It was an amazing explaination. It made me think about other problems as well. Good job guys!
the best explanation. Got the way in first 5 minutes itself.
Excellent explanation! Please make more videos on the various algorithmetic problem
Ok, will do
You are brilliant sir.Always come to your channel whenever got stuck
thanks.
using this to quick learn binary trees, super descriptive and clear, Great Work!
thx
One of the best explaination 👍👍👍👍
thx
This concept was awesome !!!
Great video
thanks
Man!...You are GOD!!..Again Best explanation on the entire internet!!
im normal
Hi Ben, thanks for another fantastic video. Just wondering if you take any requests for specific problems? Recently, I was stuck on the “Median of two sorted arrays” problem and none of the tutorials were any helpful. I also heard it’s quite a popular question. I know you probably already have an agenda in mind but it’d great if you can cover that. Thanks again for these tutorials!
hahaha yes. Thank you for asking so kindly. Yes that is a question on the very top of my mind. I am very aware of it and want to cover it but have no idea when it will happen. So much ground to cover.
No offense to Ben but search for Tushar Roy, he has explained it quite well in my opinion.
Actually XD Ben has the link to Tushar Roy's channel in his description.
@@raksstrife1233 I'll explain it better 😱😱 (try to)
@@raksstrife1233 Yeah. I mean...this is all about making resources available and I'd be amiss if I didn't acknowledge his channel since it is huge. But I want to do it better than him of course.
Like your explanations because you focus on the intuition and approach behind reaching the solution. Also, you repeat important keywords quite a bit which is helpful in understanding a difficult/new approach. Keep up with the good work :)
ok
Very clear explaination. Hope you can make an DFS explain on this!
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Really good job, amazing stuff, keep it up!
workin' on it.
GREAT explanation sir.
thx
The way you explain the Concepts are very clear... But it was very helpful if u explain the problem along with some pseudo code😀
We have a code sample up but the repository is deprecated - we only maintain backtobackswe.com now.
That moment of happiness when you come to know that there's a BTBSWE solution for the problem that you're currently stuck with!
This is very complicated explanation of the problem. To be honest I really did not understand until I manage to solve by myself. This is for those who does not understand properly from this video.
1 : define a vector which called 'result' to hold result nodes
2 : convert the given binary tree into un-directed graph.
3 : use the 'start' node as a starting vertex for breadth-first search
4 : during breadth-first search check the distance of the nodes, if their distance is equal to K push into result vector.
5 : return the result vector.
Beautiful explanation, very grateful for your videos
Thanks! This video is really helpful for me to prepare the coding interview!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
I love it, very brief explanation, much better than looking at the discussion of leetcode Lol
yeah, fuck leetcode
Awsome solution with great explanation technique. Thank you so much for the solution.
thx
thank you ben you are amazing dude i was stuck with this for 4hours and u explained it in 15 minute's thanks again
sure.
This is a great video. Very clear and easy to understand explanation. Why don't you make a playlist where you organize your videos in order(e.g. 1st video to watch and so on) for people to follow?
people have suggested this but....1.) I can't make anymore playlists...I've hit the cap....and 2.) I don't think there is any order...it is just whatever topic you are weak at...and you practice that....I think that's the optimal strategy....there can be no master order of questions because that ignores that everyone is generally different and more or less adept at different categories to different degrees
love this video! Thanks for share it. BTW the space and runtime complexity explanation was awesome! :) hehe
thanks and thanks
Thank you so much for the detailed explanation.❤️🙏
Sure!
Extra ordinary explanation
thanks lol
Hi, I still don't see how you have been able to include parent 3 from start root node 5.
Shouldn't we have to start traversing the "graph" from the root 3 before so we can know that 3 is indeed a parent of 5?
I feel like before you started implementing the solution, it was going to be a 2 step process:
- 1st traverse the tree to have the desired mapping
- 2nd graph traversal now that we can go upwards.
But then, you have just started right away at 5 with the capability of going upwards.
Where did I loose you?
Thanks! Awesome content : )
Hey, I don't remember the example in detail as I did this nearly a year ago. Could you condense the question or give me timestamps? I am rapidly responding to youtube comments
Same problem for me as well. Not able to get you when you got 3 as a parent of 5
@@BackToBackSWE : when you started adding the nodes in the hashmap, You started directly from node 5 (at 9:22 ). How did you reach node 5 directly ??.... Secondly , i am assuming that you first wrote, the code to recursively reach node 5 , but if thats the case then how will you know whose the parent of the node 5 once you have already reach node 5 ??... . I understand the point that we are treating it as an undirected graph but it still technically is a Tree which is directed in nature. I hope i am able to cleary state the problem??
yes same problem. Can you explain how to traverse through the tree from the node to create a hash table that allows any node to access their parents? Essentially the code behind how you make it bidirectional
Thank you dude. First, i thought i should use hashmap for storing distance of nodes from the target node but ur tricked help to map parenting of node that help me
Man what a terrific explanation.
thanks
So intuitive and amazing!
thanks
best resource of the question😊😊😊😊
thanks
Awsome bro ! Good explanation
thx
Good explanation but would help if the parent hash table was visualized here too. Was a bit confused due to the lack of that reference. I only say that because the rest of the explanation was crystal clear haha
Very clear explanation. The intuition and thought process helps me a lot!
Hi, I love your videos, they're very clear!
May I offer a suggestion though? Please don't put hints to the solution in the title, it spoils it when people are trying to solve it. Thanks!
Thanks! and ok haha
Awesome explanation . Thank you so muchh
sure
Always end up on this channel for some good algo explanations.
Thank you 🎉 We appreciate it. Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
Great video. Clear explanation. Thanks a ton. Love you guys. You both made it simple.
It is just me now but thank you!
@@BackToBackSWE Okay. All credit goes to you.
Thank-you!! video is helpful
sure.
Awesome tutorial . Please share the code link. I could not find it the description
The repository is deprecated, we only maintain backtobackswe.com now.
Thank you so much for this nice explanation. I should have subscribed your channel earlier. I'm having an Amazon interview next week but I feel that I'm not prepared yet.
Nice, good luck, don't let the result determine your worth
thank u so much sir and entry of ben is just awesome 🤣🤣
Thank you. Very well explained
Bro, I am new to channel but I really liked your explanation. If a code walk thought was given, it will be the best. But thanks for all
Amazing explanation.
thx
please make more videos
thanks a lot
ok
Please continue uploading videos you teach really good..RESPECT+++
ok
Extraordinary explaination Sir
thx
Thank you very much for the explanation. I could not understand the notes on leetcode.
nice
Love the idea, great solution, thank you!
sure
Thank you very much for that easy explanation.
thanks
Thanks very much for the awesome videos and detailed explanations. Really loved the series.
Wanted to ask if you can also make a video to explain the method using DFS to solve this problem? Thanks!
sure and it is basically the same
Actually, you can save some more space.
Instead of using a "seen" HashSet, you can simply remove any node you already put in the queue from the "parent" map.
That way, if you try to add a node to the queue, whether it's a parent, left or right - if it isn't in the map, you simply don't add it, since you already "visited" it.
This solution will not only remove the duplicate space, but actually reduce the space as you go on.
thanks for this
Bro, this is crazy, I've watched a handful of your videos and swore I recognized some of the classrooms you've been in. Then realized we both are from the same school lol. Class of '18 and your videos are great refreshers for studying to get my next job. Keep up the good work and go terps 🐢
thanks bro, for this awesome explanation. Keep making more videos
ok
Max comparison for binary search will be??
great great great explanation!!
Great explanation, best I’ve seen. Keep it up!!
It's really the best resource to learn
hey
great explaination !
thanks for the clear explanation. your code was even well commented & easily understandable. cheers!
cheers right back at you
where is the code though
you guys are brilliant
ye
I like how you squeeze your eyes to emphasise something :D
u deserve a lot more subscriber then that u have
Nah, it's chill
Just to clear things out: 'bidirectional' here means the children and parent of a node, unlike the more common usage where two simultaneous traversals occur (one from node u, and the other from node v).
yes, I got fancy with the title & tried to act smart
Very helpful. Thank you very much!!!
sure
Great explanation !! 🤩🤩🤩🤩