All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A Hashtable
Ғылым және технология
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given 3 things. The root of a binary tree, a single start node in the binary tree, and a number k. Return all nodes that are k "hops" away from the start node in the binary tree. Return a list of the values held at those nodes.
Complexities
n = total amount of nodes in the binary tree
m = total edges
Time: O( n + m )
This is standard to Breadth First Search. We upper bound the time by the number of nodes we can visit and edges we can traverse (at maximum).
Space: O( n )
We have a hashtable upper bounded by n mappings, a mapping to each node's parent.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Пікірлер: 465
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.
@anubhavkalia5130
4 жыл бұрын
please make more videos thanks a lot
@BackToBackSWE
4 жыл бұрын
ok
@hieungocvo1090
3 жыл бұрын
I cannot see the code for the problem
@Royceroni
2 жыл бұрын
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.
How can your content be so good man? Video after video. The best. Take a bow.
I never see your code, you explain the algo and I try to code it myself. Thanks for the great explanation
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 .
@BackToBackSWE
4 жыл бұрын
great to hear and thx
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
@BackToBackSWE
3 жыл бұрын
nice!! thanks for commenting
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 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
@BackToBackSWE
4 жыл бұрын
thanks
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!
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.
@BackToBackSWE
4 жыл бұрын
nice
Love the way you start with your thought process, brilliant. Keep up the hard work
@BackToBackSWE
5 жыл бұрын
thanks, will do
You literally put lot of effort to make us understand. Appreciate it a lot.
@BackToBackSWE
4 жыл бұрын
sure
Such a Clear explanation of the thought process and the solution ! Great one as-usual
@BackToBackSWE
4 жыл бұрын
thanks
You are brilliant, having a great gift of presenting, and also your video editing and timing is great (cutting out the right stuff). Subscribing!
@BackToBackSWE
5 жыл бұрын
thanks haha
Thank you so much for the video. Crisp and clear. No bullshit. Love videos like these!! Keep up the good work!!
@BackToBackSWE
5 жыл бұрын
thanks
You are the best tutor on youtube for dsa. Please make more and more videos to help us !!! Thanks a lot
@BackToBackSWE
4 жыл бұрын
ok
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.
@BackToBackSWE
5 жыл бұрын
Aw thanks haha, dang, the first videos suck
Such an ingenious approach ! Hats off to you mate. Keep posting :)
@BackToBackSWE
4 жыл бұрын
thanks
This is the beast channel I ever seen.THKS you and your team make the toppest resources available for us.
@BackToBackSWE
3 жыл бұрын
ye
Was stuck in this qsn for almost a day . Thanks dude!
@BackToBackSWE
4 жыл бұрын
sure
really helpful this video, the clearest explanation in KZread, thank you so much
@BackToBackSWE
4 жыл бұрын
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!
@BackToBackSWE
4 жыл бұрын
Ah yeah, memory addresses have to to be unique.
Great walkthrough! Loving these videos.
@BackToBackSWE
4 жыл бұрын
sure
Was able to solve this problem on my own after listening to your great explanation. Thanks!
@BackToBackSWE
4 жыл бұрын
sweet
using this to quick learn binary trees, super descriptive and clear, Great Work!
@BackToBackSWE
3 жыл бұрын
thx
Nice one. I like the simplicity and explanation. Thanks for that!
@BackToBackSWE
4 жыл бұрын
sure
Very clear explanation. The intuition and thought process helps me a lot!
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 :)
@BackToBackSWE
4 жыл бұрын
ok
thank you ben you are amazing dude i was stuck with this for 4hours and u explained it in 15 minute's thanks again
@BackToBackSWE
4 жыл бұрын
sure.
Only a word can describe you as a whole....... and that word is AMAZING
@BackToBackSWE
3 жыл бұрын
thx
love this video! Thanks for share it. BTW the space and runtime complexity explanation was awesome! :) hehe
@BackToBackSWE
4 жыл бұрын
thanks and thanks
Great explanation, best I’ve seen. Keep it up!!
Really good job, amazing stuff, keep it up!
@BackToBackSWE
5 жыл бұрын
workin' on it.
Yo that man Ishan hella smooth
@BackToBackSWE
5 жыл бұрын
yeah
@Travis-ko2jo
5 жыл бұрын
@@BackToBackSWE for real
@BackToBackSWE
5 жыл бұрын
@@Travis-ko2jo !!!
All the video was super cool to watch, but the humor again... stole the show!(at the end) Great Job!
@BackToBackSWE
4 жыл бұрын
thanks
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?
@BackToBackSWE
4 жыл бұрын
"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.
@123aniruddhsiddh
4 жыл бұрын
But that's not the question bro
the best explanation. Got the way in first 5 minutes itself.
Crystal clear explanation!! Thanks a ton for your efforts and time
You are brilliant sir.Always come to your channel whenever got stuck
@BackToBackSWE
4 жыл бұрын
thanks.
Amazing Explanation, thanks Benyam!!!
@BackToBackSWE
4 жыл бұрын
hey thanks
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?
@BackToBackSWE
4 жыл бұрын
We are releasing a new platform to keep everything organized today
This concept was awesome !!! Great video
@BackToBackSWE
4 жыл бұрын
thanks
Great video. Clear explanation. Thanks a ton. Love you guys. You both made it simple.
@BackToBackSWE
5 жыл бұрын
It is just me now but thank you!
@srilekha9177
5 жыл бұрын
@@BackToBackSWE Okay. All credit goes to you.
Love the idea, great solution, thank you!
@BackToBackSWE
4 жыл бұрын
sure
It was an amazing explaination. It made me think about other problems as well. Good job guys!
Awsome solution with great explanation technique. Thank you so much for the solution.
@BackToBackSWE
4 жыл бұрын
thx
This guy is so much clear in his thought process
@BackToBackSWE
5 жыл бұрын
This guy agrees :) haha
Thank you so much for the detailed explanation.❤️🙏
@BackToBackSWE
3 жыл бұрын
Sure!
You explanations are simple and easy to follow
thanks for the clear explanation. your code was even well commented & easily understandable. cheers!
@BackToBackSWE
5 жыл бұрын
cheers right back at you
@divijjain4674
3 жыл бұрын
where is the code though
So intuitive and amazing!
@BackToBackSWE
4 жыл бұрын
thanks
Beautiful explanation, very grateful for your videos
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!
@BackToBackSWE
4 жыл бұрын
sure and it is basically the same
Thank you for such a great explanation !
This is awesome. Thank you!
@BackToBackSWE
5 жыл бұрын
sure
Excellent explanation! Please make more videos on the various algorithmetic problem
@BackToBackSWE
5 жыл бұрын
Ok, will do
great great great explanation!!
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.
@BackToBackSWE
4 жыл бұрын
Nice, good luck, don't let the result determine your worth
Thanks! This video is really helpful for me to prepare the coding interview!
@BackToBackSWE
2 жыл бұрын
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
@BackToBackSWE
4 жыл бұрын
yeah, fuck leetcode
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 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
great explanation and ending, thanks Benyam!
Thank you. Very well explained
The way you explain the Concepts are very clear... But it was very helpful if u explain the problem along with some pseudo code😀
@BackToBackSWE
4 жыл бұрын
We have a code sample up but the repository is deprecated - we only maintain backtobackswe.com now.
thanks bro, for this awesome explanation. Keep making more videos
@BackToBackSWE
5 жыл бұрын
ok
Man what a terrific explanation.
@BackToBackSWE
4 жыл бұрын
thanks
great explaination !
Thank you very much for that easy explanation.
@BackToBackSWE
5 жыл бұрын
thanks
Thanks a lot for this!
You are a legend!
Man!...You are GOD!!..Again Best explanation on the entire internet!!
@BackToBackSWE
4 жыл бұрын
im normal
Great explanation !! 🤩🤩🤩🤩
thank u so much sir and entry of ben is just awesome 🤣🤣
Awesome explanation . Thank you so muchh
@BackToBackSWE
4 жыл бұрын
sure
Very helpful. Thank you very much!!!
@BackToBackSWE
5 жыл бұрын
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?
@BackToBackSWE
5 жыл бұрын
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
I like how you squeeze your eyes to emphasise something :D
Very cool!
Thank you Mr.Perfect :)
@BackToBackSWE
5 жыл бұрын
haha
Simply the best!
@BackToBackSWE
4 жыл бұрын
thanks
It's really the best resource to learn
@BackToBackSWE
5 жыл бұрын
hey
Thank you so much!
@BackToBackSWE
4 жыл бұрын
sure
Thank you!
Thank-you!! video is helpful
@BackToBackSWE
4 жыл бұрын
sure.
Hey Ben, great video! Keep up the good work. I have a request, would you please recommend a way to get good at Object Oriented design?
@BackToBackSWE
5 жыл бұрын
Eh...I mean, that's a hard thing to answer. Like...how did doctors get good at doctoring? It'd be a long history of study and learning. So many uncountable days absorbing information. All you have to do is practice. Practice coding, read books, watch KZread videos. A great book I have read and recommend is called "Clean Code: A Handbook of Agile Software Craftsmanship" by Robert C. Martin
Smooth!
Superb Explanation.
Amazing!!!
That moment of happiness when you come to know that there's a BTBSWE solution for the problem that you're currently stuck with!
wow simply awesome Thanks !!!!
@BackToBackSWE
5 жыл бұрын
sure
Very clear explaination. Hope you can make an DFS explain on this!
@BackToBackSWE
2 жыл бұрын
Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)
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
Thanks for the great video! However, I didn't understand how you arrived at target = 5 to begin with. We have to do multiple traversals then? One to identify the starting point and another to begin the iteration from the start point. Is that how this works? Or am I missing something? Or do you build the hashmap separately and then use it as a reference while working on the queue?
Awsome bro ! Good explanation
@BackToBackSWE
3 жыл бұрын
thx
Amazing explanation.
@BackToBackSWE
4 жыл бұрын
thx
Brilliant!
@BackToBackSWE
4 жыл бұрын
thanks
very amazing explanation. again. thanks.
@BackToBackSWE
4 жыл бұрын
sure
Awesome explanation , you saved my day
@BackToBackSWE
4 жыл бұрын
great
you guys are brilliant
@BackToBackSWE
4 жыл бұрын
ye