Recover a Tree From Preorder Traversal - Leetcode 1028 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem recover a tree from pre-order traversal it's actually a pretty interesting problem especially for a hard one I think it's not too crazy and I'm not going to lie today is kind of one of those days for me I'm a little bit tired but I mean who isn't so I'll still try to make the best video possible and uh by the way how's the uh mustache coming in so the idea behind the problem is similar to another variation of this where we're actually given like a pre-order and like in order traversal and then we have to kind of reconstruct a binary tree but I think that's like a binary search tree this problem is a little bit different so in case you've solved that problem before just kind of keep that in mind this one is different so we are given a pre-order traversal of a binary tree not a binary search tree so you notice that here there's no search property it's not like every value on the left is going to be less than the value at the root and the form that we given this pre-ordered traversal is pretty interesting so see it over here I'll go through what they mean by this cuz that's really what the whole problem is about so in this example here notice that we have a one after that we have a single Dash and then a two and then after that we have two dashes and then a three now there's not actually any spaces in the string like I've drawn them but I'm drawing the spaces just to make it more clear what we are given and then we are given two dashes and a four and I'll keep drawing it down here and then we're given a single Dash and a five couple dashes with a six couple dashes with a seven again this is given in the form of a single string no spaces and what this represents is first of all it's straightforward to recognize that the numbers themselves represent the values of each node and this example is pretty simple but recognize that there could be multi-digit values that's one thing you have to recognize so this could have been a 20 or you know 222 something like that I think it's bounded by like a th so that's a max value any node will have we won't have any more than a thousand different nodes but notice that we're also given these dashes and these dashes are going to be very useful for us each Dash will tell us what the depth of that node is so however many dashes come before a given value will tell us the depth of that node this is very useful for us because it tells us that first of all like the first value it's just a one there weren't any dashes that came before it so we know for sure that this is going to be the root but actually we didn't need the dashes to tell us that that was going to be the root we know that the way pre-order traversal works I mean if you're solving this hard problem I hope you do know how pre-order traversal works if you don't consider checking out some courses on EOD iio I'll try to briefly explain it right now but basically it means that like the way we would Traverse this tree is first we Traverse the root then we would recursively run pre-order traversal on the left sub tree and then after we're done with that entire tree we would run pre-order traversal on the right sub tree so recursively this is how it's going to work we're on the left side we start with the root we do that first and then we go to the left side of that and then we see three we do that first so you can see that the order that we were given these in 1 2 three matches that of the pre-ordered traversal and after that we do four and then we're done with the left side so then we move to the right side five and then six and then seven so that matches the input order so so far everything seems very simple it seems like everything is given to us it doesn't seem so bad and it actually isn't but there are a couple things you do have to notice why would they be giving us these dashes in the first place there must be some level of ambiguity from just a single pre-ordered traversal it's probably not going to be enough for us to take this traversal and then rebuild the tree that's what we're ultimately trying to do rebuild a binary tree and then return the root of that tree again these dashes will tell us the level of each node so we see that of course one will be the root this will go on the second level the second level can only have up to two nodes anyway so we see that this is a node that will go on the second level and of course this is a node that'll go on the second level as well and then we can see all four of these nodes will go on the fourth level of course the dashes alone do not give us enough information on where to place the node so we need to use a combination of these dashes as well as the fact that this order is a pre-order traversal to decide the correct positions but isn't it possible that even with that information there could still be some level of ambiguity and actually it is let me kind of just give you a very very simple example Le what about this okay this tells me that I have one as my root this tells me that one has to have a child of too but I don't know if it's going to be the left child or the right child right you have no idea pre-ordered traversal would Traverse this tree here which it looks like this the exact same way as it would Traverse this tree where we had everything on the right side so how do we know well they actually make it very easy for us they literally just tell us if a node has only one child that child is guaranteed to be the left child so we can definitely use that information to our advantage that would make this very clearly to be this tree it would look like this one is going to have a child of two a left child and then for this node three I mean there's nowhere to put it on the right side it has to go over here and two again we're not going to make it a right child of two it only has one child so we would make it a left child of two so that's more or less enough information to be able to solve the problem these are all the observations that you need to make now the first thing I thought of after processing all of this information was maybe that we could just do some kind of level order traversal that might be like the easiest way because if I could just go through and a parse the input string and then determine okay we're going to have one at this level we're going to have two and five at this level and three and six on this level and four and seven on this level then maybe I can somehow just put the nodes together and maybe I can do some kind of bias where then I can choose the nodes to go on the left side well that would be ignoring the fact that the order of these elements was again the pre-order traversal so that's why it's not going to work how do you know if seven should be a left child of six and how do you know that seven shouldn't just be a right child of three our level order traversal would not give us enough information to do that and so that's kind of when I realized that probably the way to solve this problem is to go through the input at least one possible way that I thought of was okay I know that tree traversals can be kind of simulated with a stack pre-order traversal should be a doable with that and so somehow we can scan through the input and I'll be honest my thought process for this was just to try this and just figure out the little details as I went and it just turned out that my code that I just kind of sloppily threw together it did pass it did work and it was actually the optimal a linear time solution so that's kind of what I mean by when I say this is one of those days where it's hard for me to really put a lot of effort into think about it from your guys' shoes if you were not able to kind of arrive at this solution but I think this solution isn't super crazy for a hard problem as I kind of just try it out let's just try out the sack solution figure out the little things as we go and hopefully it'll make sense to you I'm going to try this on the second example cuz I think it's a bit more difficult so knowing what we know this is why the stack Solutions seemed appealing to me because we could try something like this where we a parse the input we see the first uh number and we see that we haven't seen any dashes before it we can just have a single variable to keep track of how many dashes we've seen as we parse the string that's really not the hard part of this problem like so far we've seen zero dashes so this is our node this is the value and there could be multiple digits so we might keep reading them until we no long longer see any digits connected to this it's just a one right now so it's pretty simple so we have a one we can create a tree node of one and we can add it to our stack so I'll just draw it like this like as a node and then we'll keep parsing the string now we see a dash there's a single Dash so we'll keep track of that we've seen one dash so far and then we see another number it's two so that's kind of always going to be the case I mean can you imagine a tree where they with the rules that they gave us where we're going to have a node and it's not going to have a left child I mean that has to happen like that's guaranteed to happen if we have two nodes in the tree we're never going to have a tree that looks just like this so so far so good we take now the next node that we've seen to there was one dash that came before it so we know that this node is on the next level and we see that like our previous node which was the root it does not already have a left child and thus we're going to take two and add it to the stack but we're also going to have ended up connecting this like with the two node so just keep that in mind even though I'm just drawing the stack we are sort of building the tree as we go as well I'm going to keep parsing and now is when things actually get interesting now is when there could be a junction in our solution there could be two different possibilities one is the possibility that occurs right now we see two dashes and a three so this is where keeping track of the dashes is actually going to be useful so we've seen two dashes and then the value for our node is three we will of course create a node for three and the fact that this node is on the next level means we're going to take the node and now add it to the stack and again with the previous node that was on the stack we're going to connect its left pointer to three so that was one possibility can you please take a second to tell me what the other possibility would be this is a hard problem you should be able to figure it out what would the other possibility have been well if this node two did not have a left child well then it's guaranteed to not have a right child either so again you tell me which other place could we have possibly inserted a Noe if not here or here then the only place would have been here so what if there was only one dash that came before the three and not two how would our solution have been different try to answer it on your own but if not I'll answer it for you if we had just one dash and the value was three our solution would have to have been different we would have then saw that this node has to go on the second level it could not be connected to this node it would have had to be connected to the root node now how is that going to work with our stack based solution what's our stack going to do well isn't it true that our stack should kind of tell us like a path it should tell us how deep we are I mean that's how Stacks work that's how recursive Stacks work as well so if you're doing this recursively the recursion is going to be doing the exact same thing it's going to tell you how deep you are in the tree so really we can use the length of our stack to sort of tell us the depth and we can compare the depth with the number of dashes because we know the number of dashes basically tells us the depth of the current node that we're trying to insert so if I see that my depth my number of dashes is equal to one then I can say keep popping from the stack while the length of the stack is greater than the number of dashes keep popping from the stack so in this case we're only going to need to pop once we pop this guy and then we're good now the number of dashes matches the number of nodes in our stack and that's good because now we can take the next node three push it to the stack and then we'll see that one already has a left child so let's connect Its Right pointer to three so that's more or less how to solve the problem I think the rest of the things are just going to be like implementation details in the code you can do those many different ways I'll show you one way to do it um but just to kind of run through the rest of this example so let's just run through like the original example so we saw that we had two and then we had uh three which was at the next level so three then would have just been pushed to the stack and then we would have connected the pointer as well and then we would have kept going we see three dashes and then the four so we see that the length of the stack is not greater than the number of dashes of the current node which is four so it's fine we don't have to pop anything just add four once again and of course connect the left pointer of the previous node the previous node that's on the stack first the last node that was on the stack is going to be connected to the current node so now it's going to get more interesting now we see one dash and then the five so Dash five now we definitely need to pop from the sack keep popping from the stack while the length of the stack is greater than the number of dashes so this time we will have to pop three times from the stack that's basically telling us that now we've gone as far deep as we can and we just want to like pop pop pop and come back to the root so now we can start filling in the right side now had this been like a Double Dash five then we would have just needed to pop twice because we po this and we pop this and the Double Dash tells us that now this Noe is going to be inserted over here and the reason for that is because it was a pre-order traversal remember like this input was pre-order we're using the fact that it's a pre-order traversal and the fact that we're always inserting nodes first and the fact that the dashes tell us the level of each node we're combining all of these facts to arrive at a cohesive solution so that's kind of like my thought process at least and now that we've popped these three we will add five we will connect the right pointer and then we'll keep going now we see two dashes and a six so that's fine the length of this is not greater than the number of dashes so go ahead and insert six and this time six should be the left child of five because five does not have a left child so it makes sense if you see the picture here I'm just kind of filling it in like this now and lastly we'll see three dashes and a seven so there's three nodes on the stack no need to pop anything go ahead and add seven and connect the left pointer uh just like that then at this point we're done so we've built the tree how exactly do we identify the root and return the root well if you notice the way like this logic is working we're never going to end up popping the root from the stack so we can always just return the first node that we added to the stack the stack is going to be basically an array we can just index it to get that value and just return that so this way I believe this solution is linear time I don't know exactly if I'm doing anything fancy with like the string parsing in my solution but I don't think I am and I think it is a linear time solution for the stack even if you're not counting the space that's occupied by the result of the tree the stack still takes space so if you want to see my super authentic a thought process this was it this was my solution that I just kind of threw together so let's code it up now just a couple of variables I'm going to keep track of the number of dashes I'm just going to call that Dash or I guess plural is fine and really this is going to tell us the depth of a given node and we're going to have the stack which is going to be an array and we're going to have our variable I which is going to tell us what index we're at in the input string that we're trying to parse so I'm going to do this while I is less than the length of the input I'm going to check a couple things I'm going to check if the traversal uh the character is equal to the dash then just go ahead and increment the number of dashes and increment I otherwise we can do this we know the character is a number so we want to just get all the characters all the digits of that number so I'm going to have a separate pointer which I'm going to say J is equal to I while J is in bounds and the character is not a a digit or rather it's not a dash so that means it is a digit we will be incrementing our pointer J so once this Loop stops either we've reached the end of the input string or we've reached a dash either way we want to just get all the characters from the I pointer to the J pointer and get the digit that that represents so we can get the substring by slicing like this in Python from I to J J is non-inclusive convert that string into a number like this with Python and then we'll call that our value and this value we want to use to create a node we can call the tree node Constructor that they've kind of given us the definition for up above just passing in the value and now is where things get tricky if you're new to iteratively implementing something like this it might take you some trial and error I think I actually had like one or two bugs when I was uh implementing this but the first thing to do is recognize we want to add this node to the stack but we don't know which position to add it to and we also want to connect this node to possibly the previous node so let's do this while the length of the stack is greater than the number of dashes we might need to pop from the stack so we'll just do stack.pop after we've popped all the necessary nodes we maybe need to connect this node to like its parent unless of course this node is the root I think this is where I actually had the bug I initially tried something like this where I said if not stack -1. left then do this stack of ne1 left is equal to the node that we just created now what does this code mean it's saying the last node that we added to the array that's what negative 1 means in Python if the left node or the left pointer is null that's what the KN means then take the left pointer and assign it to the current node that we just created but what if the stack is empty that's what I did not account for so we can actually fix that pretty easily like this stack and that now the other case is else if the stack is non empty then we just want to do this except we want to do it on the right side so you can just change this to the right pointer now after we've done that we do have to make sure that we take the current node and add it to the stack so we can do this and this will happen regardless of this executed or not cuz we might be adding the root node to the stack and also just some like basic things to not forget on are to update our I pointer since we iterated through all the digits we might as well move I to be J now and we can also reset the number of dashes back down to zero because now we've just processed the current integer the current node so we can reset this to zero so then we can recompute it up here and I believe this is actually it I was surprised that this worked but I do think it does we can return stack at zero and unless there's some bugs or typos here I will go ahead and give this code a run and yeah you can see here on the left side it works it's pretty efficient if you found this helpful check out NE code IO for a lot more thanks for watching and I'll see you soon