Step-By-Step Directions from a Binary Tree Node to Another - Leetcode 2096 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve a problem stepbystep directions from a binary tree node to another the idea is we're given the root of a binary well it's not a binary search tree it's just a regular binary tree and that's very important so there's no sorted property with this tree and we're also given a start value and a destination value so both of these nodes are guaranteed to exist in the list so I think this is actually the start this is the end both of them are guaranteed to exist they're both guaranteed to be different and we want to find the shortest path from one to the other now shortest path that's not exactly going to be the hard part because the straightforward path will be the shortest path so it's not like we're going to do something like that we're just going to go here we do have some pretty nice examples this time because there's a couple things to notice in the first example there's the root node and this is the node that connects the shortest path that may not always be the case suppose um this was the start and this was the target then this is the shortest path doesn't necessarily go through the rout so that's something to keep in mind now from this example if you've solved a few other elak code uh tree problems you might have an idea look at the common node connecting them there's going to be some node that the path runs through maybe if we can find that node then then we can find the connection between them and that's actually very valid you're thinking of I think the leak code problem is called lowest common ancestor and uh the only reason I actually know that is because it is one of the famous problems in my neod 150 list and I have a pretty deep understanding of these 150 problems and I always tell people that if you have a really deep understanding of a small subset of really good problems you know then you can potenti solve thousands of problems cuz there is a lot of overlap between them now admittedly the problem we're solving today is definitely more difficult than this one this one is relatively straightforward but still if you can find the lowest common ancestor between them it seems like there's probably a solution because then we can you know find a path to the node in one sub tree it's either going to be the start or the destination and the other sub tree we can find the other value there is one Edge case though and thankfully the second example actually does make it pretty clear it could be possible that this like the node that we said the parent node that the path has to run through it could be either the start or the Target or the start or the destination sorry because look at the second example one node is a parent of the other we don't have to worry about the case where both nodes are the same that's never going to happen but one could technically be a parent of the other so if I'm being completely honest with you even though I realize that the lowest common ancestor might be able to solve this problem for us I didn't really think too deeply about how it could do that because off the top of my head it just seemed like it even if it's possible it's going to be kind of painful to cat up so I thought like okay I know that this probably could help me solve the problem but let me try to think if there is a potentially easier way because we only have two nodes I thought okay if I can from the root somehow Run a search algorithm we can't do like the regular binary search tree traversal which would generally run in log end time because we have like a sorted binary search tree we can't do that for the start and destination values we do have to do a Brute Force depth for search or backtracking whatever you want to call it you have to kind of go through the entire uh tree but if we can do that if we can find the value the node with a value three let's get a path to that node and maybe we can also get a path to the destination node and before I go any further let me explain what actually returning in order to connect these two nodes the path has to be returned in a very specific way we start at the start value so it's not symmetrical we can't like give a path like this I mean technically you could and then maybe you could reverse it or you know do some kind of processing after the fact but let's stick with the straightforward way for now we have to start here we have to end here and basically when we're moving up we use the character U so we go up obviously here we go up obviously there and then to get to the destination we go right and then we go left so it looks to me that the path is going to be up up right left that is the result for this problem so now how do we get there well intuitively before I even wrote it out I kind of knew that okay now it's all starting to make sense the lowest common ancestor actually is going to be useful for us watch this because that's let me think of some better examples I'm going to be constantly changing like what the start and end node is in this example just to kind of make it clear CU we're going to go through several different you know scenarios this is just kind of a small binary tree for us to illustrate several examples but the idea is this suppose this is the start and suppose this is the target the path to the start is going to be uh left left the path to the Target is going to be right right so now that we have that we have the path to the start is left left we have the path to the Target is right right how do we get it in the form that we want the result the correct result should actually be up up right right how do we get it into that form well basically it's actually pretty easy isn't it we just take the path to the start node and replace every one of these with the Up character at least in this example right it doesn't matter whether we went left or right let me change the example for a second let me say that actually this was the start node so actually the path was left right and now the path to the destination is still right right that doesn't change anything we still have to go up twice the result is still up up right right at least in this kind of example now let me give you a counter example where that doesn't work let me give you this example uh this is the start and this is the target path to the start is going to be left left path to the Target is going to be left right so the first path to the uh start is left left path to Target is left right now are you kind of noticing anything like I said lowest common ancestor do you think we can find the lowest common ancestor from these inputs of course we can we have a pointer that iterates character by character We compare if the two characters are the same obviously from the root we're going to the same node so it's not until we find the first differing character that we have found the lowest common ancestor until that point we are basically going in the same direction to find both of them okay how does that help us solve the problem though well basically we as we iterate that pointer we ignore these I don't care about it from the first or the second array because now what we can say is the result is going to be up right so I take every remaining character from the first array and replace it with a u and I just take everything from here and concatenate it to that so the result is up right we're getting very close just a couple more edge cases to consider remember the case of course where suppose this is the start and suppose this is the destination okay to get to the start is going to be left left to get to the destination is just going to be one left okay so now it's kind of tricky the arrays are of different size we're still going to follow the same idea though go character by character these two are clearly the same okay so now wherever we ended we're at the lowest common ancestor do the same damn thing okay I don't know why I said damn sorry uh but take this everything remaining from here replace it with a u take everything remaining here concatenate it uh that's it literally that's it just go up once this is the result try to do the opposite this is the start node the parent is the start and the child is the destination how does that work well to get to the start we have one left to get to the destination we have two lefts same thing go character by character these are the same boom okay we ran out of characters from here so what do we do replace everything with a u there's nothing left take everything here concatenate it to that so this is the result left from start go left that's it I think we've pretty much ran through every example if there's one last example you wanted to try your yourself maybe try something like this where the arrays are going to be of different lengths maybe uh this is the start and this is the destination try that out maybe try flipping them but I think you'll find that the algorithm that we're using works the same so in summary we're going to run a DFS to find the path that gives us the start that's going to be Big O of n because we do have to potentially go through the entire um tree because first you know from here we're going to try looking over here is the start somewhere here if might not be then we might have to go to the right side so we're going to have to do that twice to find the path to the start and the destination but once we have those paths the solution is going to be kind of trivial like I said we're just going to be kind of concatenating those two arrays and in terms of space complexity I think it's also going to be o of n just if we're counting like the output like those arrays I was talking about especially that's probably going to be the bottleneck but in any case this is pretty efficient I think okay so let's get into it first I'm going to start with that helper function that I talked about DFS it's going to obviously keep track of what current node that we're at we're going to keep track of what current path we're at and also to make this extensible because we're going to use it twice we want to know what Target are we looking for we're going to pass in this the first time and this the second time to get the path to each of those nodes and if you're still not convinced to use Python yet I bet this solution I'm about to show you might convince you honestly sometimes I'm surprised by how easy python makes things but first of all if we reach null so if not node let's return an empty string an empty string is evaluated as false in Python and we're going to use that to our advantage so just keep that in mind the other thing is of course if we actually reach the target if the value is at the Target then let's return the current path that we are maintaining is the recursive step we don't know where the result could be it could be there on the left side or the right side so let's run a DFS on both sides no do left a passing in the path pass in the Target and doing the same thing for the right side now obviously it's not going to be this simple we do have to keep track of what the path is so if we're going left well first of all let me change this to right but if we're going left we should probably say path. append the character left at the very least we should do that and then before we go to the right side we should probably pop that we should say path. pop that character that we just appended here and replace it with a right character okay getting closer but at what point are we going to return the result like we're looking for a particular node if we find it from this path then we should return we don't really need to do the second recursive call how do I know that well based on my base cases here if the result is nonnull or non-empty like a non-empty string then we have the result so I'm actually going to take the return value of the first recursive call assign it to a variable which which I'm going to call the result and if result is true then I'm going to return that result so this is the first recursive step pretty much the same thing for the second one so get the result here and then if it's nonempty go ahead and return it I'm only putting this if statement on the same line just because I don't want to run out of like vertical space I want to be able to show all of this to you at a single time but you know it's not a big deal if you take this and put it on the next line I don't really care now you might be thinking in which case is neither of these going to return like why do we need out here a another return statement where I return an empty string and even more than that why do I need to do this why do I need to say path. pop well think of it this way suppose we start at the root here suppose three is the target well we're going to get to two eventually then we're going to go left it's not the result then we're going to come back to two then we're going to go right it's still not the result well then we need to pop back up and pop back up here and then we need to go to the right side that's why even though we don't find the result in the right sub tree or the left sub tree from this current node we still might have the result somewhere else in the tree so that's just the example I wanted to make it clear okay now for the easy part to be honest let's call DFS pass in the route pass in an empty list and pass in the start value do the same do the same thing with the destination value let's maintain the result of each of these in a separate variable I'll call it start path and I'll call it destination path and now remember what we want to do is find the first differing character I'm going to have a pointer I is going to be zero I'm going to say while I is less then we don't want it to go out of bounds so we don't know which one of these lists is shorter so I'm going to take the length of the first one and the length of the second one and then I'm going to take the minimum between them like this and I probably could add like a second condition in the loop here itself like in the condition itself but I'm just going to put it inside just for readability so I'm going to say if the character is not equal to the one in the other array as well if there is a different character let's go ahead and break out of the loop otherwise don't forget to increment your pointer at the very least you'll need this line inside of your Loop but you know if I wanted to put this condition um outside of this loop I could get rid of this I could put it over here and I could change this to an equal so while they're equal continue basically this is the inverse of this one so anyways almost done with this scroll down now you might be thinking well how can we code this up in most languages you'll probably need a loop to do it but python it just makes it so easy you're not even going to believe it the result is going to be this um how many U's do we need we need this many U characters basically how many characters are remaining in the start path well I'm going to take basically the length of start path starting from index I it could technically have zero characters remaining and believe it or not then if this was zero and we're multiplying Zero by this that would result in an empty array so this is the first portion this tells us how many steps up we need to go the second portion I'm going to add to this is what are the characters remaining in the destination path it could be empty or there could be some characters in it basically just take Des path do the slice starting from I just like that in Python and this is your result why do I even need to assign it to a variable when I can just go ahead and return it like this so I know I did a few like python tricks in this video I don't think most of them are going to be crazy to translate into other languages like you'll just need extra code to do it to be honest it's not that it's difficult it's just going to be more verbose for you probably oh actually I did uh forget something that's kind of embarrassing so we actually don't want to return it in the form of a list so we want to return it as a string and thankfully python makes that pretty easy as well I didn't do that on purpose by the way that mistake I'm talking about um so we can do this an empty string. join with the list that we passed in here um if you if it makes it clear I can maybe put this into a variable at this point I guess that's assigned to result then we pass result in here and then that's what we end up ultimately returning I'll run this you can see it works and it's pretty efficient thanks for watching if you found this helpful check out NE code. I plan on launching python for coding interviews tonight perfect timing if you're trying to learn any of these tips and tricks I showed in this video hopefully I'll see you soon