All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A Hashtable

[@BackToBackSWE]

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]

please make more videos thanks a lot

[@BackToBackSWE]

ok

[@hieungocvo1090]

I cannot see the code for the problem

[@Royceroni]

the code isn't in the description?

[@lifealalexie]

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.

[@ishanmundra6891]

Yo that man Ishan hella smooth

[@BackToBackSWE]

yeah

[@Travis-ko2jo]

@@BackToBackSWE for real

[@BackToBackSWE]

@@Travis-ko2jo !!!

[@bestsaurabh]

I never see your code, you explain the algo and I try to code it myself. Thanks for the great explanation

[@mrunaldave6781]

How can your content be so good man? Video after video. The best. Take a bow.

[@jhamukesh998]

You are the best tutor on youtube for dsa. Please make more and more videos to help us !!! Thanks a lot

[@BackToBackSWE]

ok

[@shashwatshukla6492]

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.

[@grovervishal591]

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]

nice

[@Sky-nt1hy]

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]

nice!! thanks for commenting

[@sammynochains3455]

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]

great to hear and thx

[@AnjalySB]

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]

thanks

[@vedantiyangar151]

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]

Ah yeah, memory addresses have to to be unique.

[@nelsonthekinger]

All the video was super cool to watch, but the humor again... stole the show!(at the end) Great Job!

[@BackToBackSWE]

thanks

[@yifanzhang1211]

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]

Aw thanks haha, dang, the first videos suck

[@pinakisaha9917]

You literally put lot of effort to make us understand. Appreciate it a lot.

[@BackToBackSWE]

sure

[@parthkhanna8542]

Only a word can describe you as a whole....... and that word is AMAZING

[@BackToBackSWE]

thx

[@shwetabhardwaj1131]

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]

We are releasing a new platform to keep everything organized today

[@caseyschneider1974]

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]

"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]

But that's not the question bro

[@jamestak1526]

This is the beast channel I ever seen.THKS you and your team make the toppest resources available for us.

[@BackToBackSWE]

ye

[@jamesfifth8479]

really helpful this video, the clearest explanation in KZbin, thank you so much

[@BackToBackSWE]

sure

[@kakashisenpai99]

Was stuck in this qsn for almost a day . Thanks dude!

[@BackToBackSWE]

sure

[@abhilakshsharma1275]

Such an ingenious approach ! Hats off to you mate. Keep posting :)

[@BackToBackSWE]

thanks

[@dankokozar]

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]

thanks haha

[@quantum598]

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'

[@tapasu7514]

Love the way you start with your thought process, brilliant. Keep up the hard work

[@BackToBackSWE]

thanks, will do

[@spicy2112]

Thank you so much for the video. Crisp and clear. No bullshit. Love videos like these!! Keep up the good work!!

[@BackToBackSWE]

thanks

[@manojrajasekar6035]

Such a Clear explanation of the thought process and the solution ! Great one as-usual

[@BackToBackSWE]

thanks

[@amitupadhyay6511]

the best explanation. Got the way in first 5 minutes itself.

[@uppubhai]

This guy is so much clear in his thought process

[@BackToBackSWE]

This guy agrees :) haha

[@AdwantGoutam]

Nice one. I like the simplicity and explanation. Thanks for that!

[@BackToBackSWE]

sure

[@sujithameriga7348]

It was an amazing explaination. It made me think about other problems as well. Good job guys!

[@FreddGuillen]

love this video! Thanks for share it. BTW the space and runtime complexity explanation was awesome! :) hehe

[@BackToBackSWE]

thanks and thanks

[@ricardobaeta3184]

using this to quick learn binary trees, super descriptive and clear, Great Work!

[@BackToBackSWE]

thx

[@prachurjyabasistha4682]

Man!...You are GOD!!..Again Best explanation on the entire internet!!

[@BackToBackSWE]

im normal

[@nayanikau2059]

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]

ok

[@mrkyeokabe]

Was able to solve this problem on my own after listening to your great explanation. Thanks!

[@BackToBackSWE]

sweet

[@mananarora5027]

This concept was awesome !!! Great video

[@BackToBackSWE]

thanks

[@who_fkn_cares]

Great walkthrough! Loving these videos.

[@BackToBackSWE]

sure

[@suhasnayak4704]

Amazing Explanation, thanks Benyam!!!

[@BackToBackSWE]

hey thanks

[@raghavmittal5352]

You are brilliant sir.Always come to your channel whenever got stuck

[@BackToBackSWE]

thanks.

[@ruditrahul3638]

Can anyone share me the code link!!! Its not there in the description

[@pkboolean]

Great explanation, best I’ve seen. Keep it up!!

[@rbragdish]

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!

[@anarce]

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!

[@BackToBackSWE]

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]

No offense to Ben but search for Tushar Roy, he has explained it quite well in my opinion.

[@raksstrife1233]

Actually XD Ben has the link to Tushar Roy's channel in his description.

[@BackToBackSWE]

@@raksstrife1233 I'll explain it better 😱😱 (try to)

[@BackToBackSWE]

@@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.

[@pabloruiz577]

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 : )

[@BackToBackSWE]

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

[@praveerdas4817]

Same problem for me as well. Not able to get you when you got 3 as a parent of 5

[@manujetley2800]

@@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??

[@kennyhar7179]

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

[@tingtingzhao7482]

Very clear explanation. The intuition and thought process helps me a lot!

[@JimmyCheng]

Really good job, amazing stuff, keep it up!

[@BackToBackSWE]

workin' on it.

[@shreejitnair2174]

Man what a terrific explanation.

[@BackToBackSWE]

thanks

[@avoo1d]

I love it, very brief explanation, much better than looking at the discussion of leetcode Lol

[@BackToBackSWE]

yeah, fuck leetcode

[@anuragagnihotri5238]

You explanations are simple and easy to follow

[@SUNILKUMAR-gy1je]

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]

sure.

[@tulikamal]

Excellent explanation! Please make more videos on the various algorithmetic problem

[@BackToBackSWE]

Ok, will do

[@yuhaoliao3270]

Thanks! This video is really helpful for me to prepare the coding interview!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@poojabennabhaktula4883]

Beautiful explanation, very grateful for your videos

[@lifehacks9450]

u deserve a lot more subscriber then that u have

[@BackToBackSWE]

Nah, it's chill

[@srilekha9177]

Great video. Clear explanation. Thanks a ton. Love you guys. You both made it simple.

[@BackToBackSWE]

It is just me now but thank you!

[@srilekha9177]

@@BackToBackSWE Okay. All credit goes to you.

[@eyeamkd]

That moment of happiness when you come to know that there's a BTBSWE solution for the problem that you're currently stuck with!

[@apollossevere8602]

Bro, where the heck is the code in the description?!??

[@pushkardureja6863]

One of the best explaination 👍👍👍👍

[@BackToBackSWE]

thx

[@ananya___1625]

Crystal clear explanation!! Thanks a ton for your efforts and time

[@Dyslexic_Neuron]

Awsome bro ! Good explanation

[@BackToBackSWE]

thx

[@JustSomeYTChannel557]

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.

[@BackToBackSWE]

thanks for this

[@sahukarinaveenkumar3188]

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]

We have a code sample up but the repository is deprecated - we only maintain backtobackswe.com now.

[@fiazB]

Where is the code? I could not find it in the description.

[@Randomtaker]

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

[@anupkmr03]

Awsome solution with great explanation technique. Thank you so much for the solution.

[@BackToBackSWE]

thx

[@christopher48778]

how do you track the level you are currently on? would you have to push the level of a node onto the stack with it?

[@BackToBackSWE]

I don't remember this problem or the code much but yes, a tuple of sorts can be done. If I remembered this better I could help in more detail but I'm fast replying to a surge of comments.

[@JustSomeYTChannel557]

Before starting the loop on each level, you check the size of the queue, and you loop on this size, popping nodes. Once you reach that size, you simply increment the level and repeat. For example, in this example, at the beginning you push "5" as a starting node to the queue, and check the queue size, which is 1. You then loop from 0 to 1 (1 loop run) and pop the node, adding it's left, right and parent to the queue. Since you now finished the loop, you increment the level by 1 (it was 0 before, now it's 1). You now check the queue size (in our example, it's 6,2,3, so the size is 3) and you loop from 0 to 3 (3 loop runs), once this is done, you increment the level by 1 (was 1 before, now it's 2) and repeat. This way at the end of each loop, if you reach the level of K, you simply return all the current values in the Queue as you know for certain it's the nodes you're looking for.

[@ish1285]

So intuitive and amazing!

[@BackToBackSWE]

thanks

[@xckevin8718]

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]

Nice, good luck, don't let the result determine your worth

[@riyadhhossain8733]

where is the code link in the description??

[@himachaligrace844]

Max comparison for binary search will be??

[@shobhitkumar6820]

best resource of the question😊😊😊😊

[@BackToBackSWE]

thanks

[@sunginjung3854]

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]

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

[@xiaoxiao5333]

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]

sure and it is basically the same

[@jaydhanwant4072]

I like how you squeeze your eyes to emphasise something :D

[@techykush7192]

thank u so much sir and entry of ben is just awesome 🤣🤣

[@sai2ramya]

great great great explanation!!

[@cmubill]

Very clear explaination. Hope you can make an DFS explain on this!

[@BackToBackSWE]

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@anuragv400]

Great explanation !! 🤩🤩🤩🤩

[@elenadontsova4688]

Love the idea, great solution, thank you!

[@BackToBackSWE]

sure

[@satishshingade8514]

Please continue uploading videos you teach really good..RESPECT+++

[@BackToBackSWE]

ok

[@sharatchandra9198]

Extra ordinary explanation

[@BackToBackSWE]

thanks lol

[@salimzhulkhrni1610]

thanks for the clear explanation. your code was even well commented & easily understandable. cheers!

[@BackToBackSWE]

cheers right back at you

[@divijjain4674]

where is the code though

[@deathstrokebrucewayne]

Okai....Concluded....You are awesome :D

[@BackToBackSWE]

thanks

[@vineetrathee7334]

GREAT explanation sir.

[@BackToBackSWE]

thx

[@vishwashdwivedi9469]

Thank you for such a great explanation !

[@sye119]

great explanation and ending, thanks Benyam!

[@vigneshwaranr680]

Thank you so much for the detailed explanation.❤️🙏

[@BackToBackSWE]

Sure!

[@lalitkumarmehta1721]

thanks bro, for this awesome explanation. Keep making more videos

[@BackToBackSWE]

ok

[@rjkal]

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?

[@MMOlocation]

Having my series of internship interviews in about a month, been grinding leetcode, watching your vids and reading EPI for the past 1 month. Do you think 2 months of such prep is enough? I'm studying around 6 hours daily.

[@BackToBackSWE]

Depends on how ready you are, hard to gauge, only you can answer this

[@Mai_Bharatwaasi]

Thank-you!! video is helpful

[@BackToBackSWE]

sure.

[@nandhiniperiyasamy4782]

Awesome explanation . Thank you so muchh

[@BackToBackSWE]

sure

[@raksstrife1233]

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]

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 KZbin videos. A great book I have read and recommend is called "Clean Code: A Handbook of Agile Software Craftsmanship" by Robert C. Martin

[@raviverma-tj6dn]

Extraordinary explaination Sir

[@BackToBackSWE]

thx

[@Od253]

Always end up on this channel for some good algo explanations.

[@BackToBackSWE]

Thank you 🎉 We appreciate it. Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀

[@yuktikhantwal2342]

you guys are brilliant

[@BackToBackSWE]

ye

[@icosmini]

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!

[@BackToBackSWE]

Thanks! and ok haha

[@AmolGautam]

Thank you. Very well explained

[@Iliketheravens]

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 🐢