before starting this video i'd love to thank relevel for sponsoring this entire tree series the placement season is here i know a lot of you are planning to sit for companies which come on campus in case you are disappointed that the top startups like tread upgrad razor pay are not hiring directly from your campus there is an easier way to work here just register for the relevant tests conducted by reliable by an academy and you'll get a chance to apply for front-end backend and business development roles at india's top startups and unicorn companies reliable has thousand plus openings by 50 plus companies and the best thing is it's absolutely free so please make sure you check out all the links in the description and give the relevant test as soon as possible hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be solving the problem nodes at a distance k from any given target node from the free car tree series so this is the binary tree that is given to you and the target node is 5 as you can see so this is your target node and the distance is given as 2 so i want you to print all the nodes that's that is at a distance of 2 so basically from this node five the distance to i can say this is one node because if i measure the distance the distance is gonna be two i can say this is another node again if i measure the distance this is going to be a distance of 2 and i can say again this is another node which is again taking a distance of 2 hence the three nodes that are at a distance 2 are 7 4 one so i want you to return these three notes and again you can print them in any order as you wish so in order to solve this problem the first thing that comes to my mind is if we know that this is the target node then i'm requiring a distance to and that can be like at the top of this node five or it can be at the bottom of the node and the nodes that i am searching for can be at the top or can be at the bottom right that's so we know that the binary trees are pointed like in the bottom mode fashion like three will be pointing to five but from five there will be no pointer to three so we cannot actually travel from five to three or we cannot travel from two to five or we cannot travel from zero to one so we cannot travel towards the parent so that's our main concern because if i'm looking for uh two distance node from five we require to travel in the upward direction as well as the downward direction so in order to travel till the uh to the upward direction what we will do is we will mark parent pointers so let's do that so at first what we will do is we can simply do a bfs traversal okay so as you know in order to do a bfs traversal the first thing that i will be requiring is a queue data structure okay and let's uh take a q data structure and initially have this root of the node insert it into the queue so once that is done what i will do is i'll start iterating in the queue so first time i'll take three so i've taken three now three is left do we have a left of three yes we have a left as five so can i say if three is left is five i can definitely put it into my queue data structure level order traversal and at the same time can i say hey 5 your parent is no and is 3 indeed yes and can i check who's 3 is right three is right is one so i'll push on uh one into the queue and at the same time i'll say one hey your parent is three so i can definitely use a map or something like that in order to store the parent of five and parent of one perfect let's go forward and do the iteration in the queue again so at the next time i'll get five so when i have five five's left is six so i'll take six and can i seem can i say again six your parent is five perfect for five the right one is two so i'll take the right one too and can i say two your parent is five perfect so the next iteration i'll get a one so when i get a one i know on the left of 1 there is a 0 so i'll put that 0 into the queue at the same time i'll say 0 your parent is 1 perfect the right of 1 is indeed 8 so can i say 8 will be entered into the queue and eight your parent will be one perfect so one is done next i'll get six so the moment i get six does it have a left no does it have a right no so six is done next i'll get two two does it have a left yes that's seven so i'll take seven and put it into the queue data structure at the same time i'll mark uh seventh parent s2 two does it have a right four yes it does have four will be taken into the queue and four will be marked over here like the parent of four will be two so i'm done with two so two is also done next i have a zero so when i take zero does it have a left and does it have a right no next i have eight does it have a left does it have a right no next i have seven does it have a left does it have a right no next i take four does it have a left does it have a right no so once i have done one level order traversal i think i can have all the parent pointers like from five i know who's the parent from two i know who's the parent so if i have to move from two till the upper direction two can go to five five can go to three and then i can go on from three to one so i can actually traverse in the bottom as well as in the proper direction so we're sorted with that so the parent pointer is done now we will move to finding out the notes at a distance k so the first step is marking the parent pointers and you can use an hash map in order to store the parents of every node now since we have marked our parent pointers now we can move upward and downward now the task is to figure out the nodes at a distance to from this uh target node right so there can be two kind of questions they can directly give you the address of this node unless they can directly give you the tree node reference or pointer whatever you can call it they can directly give you that or they will just give you the value five so in case they just give you the value 5 you can do any traversal in order pre-order post order whatever traversal you want to do you can do it and you need to figure out this pointer or address whatever you can call it or reference you just need to figure out that so assuming that you're given the address and if it is not given you can definitely search it and find it not a big deal so assuming you're given this note 5. so what you will do is you'll do a bfs traversal that is standing at this note 5 you'll try to move radially upwards downwards always okay you're going to try to move radially upwards downwards always that's the bfs traversal so and while moving you're going to count distance so initially you add five so radially move to three move to six move to two and increase the distance so gonna increase the distance till it doesn't reaches two and the moment it reaches two you can actually radially reach all the nodes that are at a distance too did not understand not an issue let's do a dry run and understand this algo so initially you will require a queue data structure which will have the target node you will require a distance which is zero and at the same time please make sure you carry a visited hash yes please make sure you carry a visited hash which actually tells you which which nodes have been visited so whenever you have a five like you have visited five so you will make sure that the visited contains the same node five and the distance is zero because the node five is at a distance zero from the node five itself so let's start off from the queue data structure so i'll take off five okay i'll take five and what i'll check is what's the upward node the upper node is three perfect the downward node is two perfect the left node the right the right node is two and the left node is six can i say they are all at a distance of one so i'll linearly increment the distance to one like i'll just increase the distance to one when i'm doing a radial radially outward like outward direction movement so three uh first uh two then six then three uh the order can be anything the order can be anything parent left right left right parent you can take it in any order so when you have taken these notes please make sure you have them in your visited array which means you have visited the note 3 visited the note 6 visited the note 2. why are you scoring in the visited i'll explain you as i do the next step now in the next step what you will do is you will take all these three notes yes take all these three notes together that's two six three okay and now try to move radially outwards from all these two notes now can i say from two like why are you at two like logically speaking why are you at two because from five you came downwards so from two when you want to move radially outwards one will be the upper direction that is the parent one will be the left one will be the right so when you try to move to the upper direction that actually takes back to five from two if you go to the parent it takes back to five so there's no need to move backward in that direction because that's that's not logical that is where the visited node will help you visited node says from two if you want to go to five you have already gone so the parent is something which you will not go so two will say okay i'll go to my seven i'll go to my four so i'll go to seven and i'll go to four that is absolutely perfect so once you've gone to seven and four please make sure you have that in your visited array now next time you come to six six says my parent is five which has already been visited because i came from five so there's absolutely no point to go back to five does it have a left no does it have a right no perfect three the three doesn't have a parent it doesn't have a parrot so it will not go does it have a left yes three is left is five itself so will it come to the left obviously no because that's already visited will three go to the right yes that's one because that's not visited so i'll go to one yes i'll go to one and the moment i go to one i can push that into the queue and i can mark that as visited so i can say from all these three notes yes all these three notes in the next iteration i made sure i did radially move outward by a distance one hence the distance will increase by one that's that means the distance will now be two so this iteration is over let's move to the next iteration now the moment i try to move to the next radially outward notes i see that the distance is already two so well it makes sense to move radially outwards no because i actually wanted the notes at a distance too and i've moved by a distance too as of now so there's no need to move any further upward left or downward hence i can say the notes currently yes i repeat the notes currently in your q data structure can be said as the nodes at a distance of 2. hence i can just take out the elements from the queue data structure i can put them into some arraylist or a vector whatever you can call and i can return them as the answer that's what my answer is going to be perfect so if i summarize the approach first point was to make sure that you have parent pointers second point was to make sure you keep on moving by one distance every time upward leftward and downward and at the end whenever the distance was equivalent to k you stop and the notes you have reached will be your notes that are your answer so this is how you get the notes at a distance of k so as usual the c plus plus code is on the left and the java code is on the right so you can follow any of the codes and you can easily understand because they are almost identical so we have this uh vector of end we are requiring the resistance of k we are given the root uh given the target and we are given the k so as you can see uh the address or reference or point of whatever you can call according to c plus plus in java the target is given to you so what we initially do is we create a map so this is the parent pointer map like i told you we have to store every node's parent so we just have a map for that and i call the smart parents function so let's check out the smart parent function so what we do is we simply do a level order traversal by taking a cue we insert the root and we get the like we do an iteration on the node and every time i get a left among the left parent as the node itself and then i push the left similarly i do it with right so once i have done this function i can say my parent is ready right my parent is ready so first step is completed that is getting the parent ready simple mark the left mark the right sparring so we're done with that next what is the next step radially travels upward leftward and rightward by a distance one every time let's see how we do that so we have a visited map at first then we have a queue initially we started with target and we had that in the visited so we will start with the target and we have that in the visited so this is our distance like this make sure that how much radially have you moved that is curl level right after that i do the iteration in the queue so how am i doing the iteration first i take the size so if you remember for the first time you had a 5 right next time you had some notes and you took all of them remember and then you moved readily outward leftward uh rightwards into all of them so that's what i've done i've taken the size i've run a for loop basically i'm traversing in all of them together and at the same time i'm making sure if if the car level like as of now initially the car level will be zero after that level will become one after that two so if the curl level at any time becomes k so in order to understand this better you can watch this out you'll understand if it is equivalent to k you'll break out or else you'll just increase the radial outward and then move right so that's done now over here we have a size so we we travel in all of them and what we do is we check on left we check on right and we check on the pivot if a left exists if we're right exist if a parent exists and if they are not visited and if they're not visited so what i'll do is i'll take it into the queue and i'll mark them as visited i'll take it into the queue mark them as registered take it into queue mark them as visited once this is done once this is done that means once i have i traded totally and i've reached the distance k i'll break out so once i've broken out whatever is on the queue i'll take that into some vector so i've taken that into some vector at the end i can return that vector or list whatever you can call it so once i've done that i can easily say i repeat i can easily say that i have figured out all my notes at a distance k so if i talk about the time complexity can i say at first i'm using a traversal to find out the parents that's a big o of n complexity after that i am actually traversing on all the nodes that are at a distance of k right that are at a distance of k that's the second that's the second stuff so the worst case i might end up traversing through the entire tree so that's again a big o of n travis right and since you're using a hash map so we can argue on that for c plus hash map can have a login complexity for java it can have a big of one complexity so i'm not considering the hash map complexity you can consider that in your interview and you can tell the interviewer depending on the language that you're coding in so i can say for traversal this is this and if you're using hash map login you can n log and you can just do it or the space complexity first you're using a parent track right so that's a big o of uh n for that then you're using another q that's another big of n and using a visited another big of n so overall i can say the complexity is we go of n only right overall i can just summarize that to big o of n so i can say the time complexity is weak often the space complexity is big often for this uh solution so i hope you've understood the entire explanation as well as the code just in case you did please please please make sure you like this video because it took a lot of efforts to make this entire tree series also if you wish you can definitely drop in a comment that will keep motivating me to make such further series also if you're new to this channel please do consider subscribing because i'm going to bring in such more series in the upcoming future as well with this uh let's wrap up this video let's speed in the next lecture bye take care whenever your heart is [Music]