Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem construct binary tree from in order and post order traversal there's a very similar problem leak code 105 I've solved that problem before this one is similar but I think this one is slightly more difficult so as you may recall in order traversal is where we start at the root and we Traverse the entire left subtree and then we process the root node so if we were printing all of these we would print nine first then we would print three and then we would print the entire right subtree but we would do it recursively so we would run in order traversal on the right subtree itself so from here we wouldn't process 20 or print it first we would go to its left subtree print everything here there's just a single one 15 then we would print the root and then we would print the right subtree which is just seven post order is where we print the entire left sub tree first and then instead of printing the root we print the entire right subtree and then after that we print the root node so it would look something like printing 9 then recursively running post order here so we print the entire left subtree 15 then we print the entire right subtree seven then we print the root 20 and then we print the root here three so given these two traversals can we reconstruct the tree exactly well yes that's the problem statement so we assume it's possible but one thing they don't State here it's listed all the way at the bottom of the description is that every node is going to be unique and that's going to be important in solving this problem every value is going to be unique so given these two traversals what will be the root note do we even know what the root is going to be well in our post order remember which is listed down here the last node is always going to be the root by definition we print the entire left then the right and then we print the root last so at least we know what the root is we know for sure the root is always going to be the last value in the post order traversal so let's construct our tree over here we have the root that's all we know we don't know the left subtree or the right subtree but since this is a tree problem you can assume that we're going to probably be able to do this recursively we want to now build the left subtree or maybe build the right subtree how do we do it well once again let's go to our handy dandy post order traversal remember how we Traverse this in post order we did 9 then 15 then 17 and then 20 and then three notice how the second to last node is always going to be the right child of three well assuming it has a right child if it doesn't have a right child then probably the left child is going to be the second to last value in the post order traversal but let's assume that 20 is the right child let's assume that the second to last is going to be the right child or instead of assuming how do we know if it is or not well let's remember we do have additional information we have an in order traversal as well let's take that three that we just used because the three that we used tells us something it tells us how many nodes are going to be on the left side of it and how many are going to be on the right side of it not using the post order but using the in order traversal we know because take a look at the in order traversal this is what it is we know that the three goes here and this is why it's important that every value is going to be unique in the tree because if we had multiple threes then we wouldn't have this information but since there are unique values here we know the 3 is right here we know based on in order traversal everything on the left side here is going to be in the left subtree we don't know exactly where but we know that and we know everything here is going to be in the right subtree we don't know the exact structure but we at the very least know that so now this is kind of how we are going to build this recursively and this is going to be a bit tricky but should we build the left subtree first or should we build the right subtree first this is why the fact is important that the second to last note in the post order traversal is going to be the right child if it exists that's why we're going to attempt to build the right subtree first and we know for sure actually in this case that 20 is going to be the right child of three because our in order traversal tells us that the right subtree is non-empty if our three value here was actually all the way over here then we would know that there's nothing to the right of of it therefore the right subtree is empty but it's not it's in the middle therefore we do have some values in the right subtree so now recursively we are going to try to build the right subtree but how exactly are we going to do that well we should probably pass in this subarray as the in order portion of our subtree for the post-order traversal for Simplicity we're going to pass in the entire array because what we know is we're always going to be popping from the last value in the post order traversal so this keeps it simple for us and recursively we're just going to repeat the steps now we're going to pop from the post order we're going to get that 20 we know it's going to be the root of this sub tree and then the in order portion of the array that we passed in which was going to be 15 20 and 7. we know these nodes are going to make up this subtree we're going to find the 20 value which goes right here and we're going to see yes we have a a left subtree with just a single node and we have a right subtree with just a single node so then we're going to try to build those sub trees we're going to start with the right subtree first as usual once again now we're going to pop from our post order traversal notice how it's that exact same seven that we were expecting so we put that 7 here and the in order portion of the array that we passed in when we made this recursive call was just seven since we have seven now we look to the right of seven there's nothing there we look to the left of seven there's nothing there so we're pretty much done with this portion of the subtree we're gonna pop back up if you remember this is the portion of the in order traversal that we passed into this subtree we already made this uh 20 we made the seven now 15 is going to be the left child and notice how when we pop from post order traversal we already popped these three values when we pop 15 it's exactly what we were expecting so we put 15 here and then we're done with this sub tree so then we pop back up up to the root and remember from here we wanted to build the right sub tree first because that made it easy with our post order traversal now we're going to build the left subtree and when we pop from post order to build that we get the nine that we were expecting so this is not super easy to come up with but you can see it does make sense the reason I was able to solve it so easily is because I solved the previous one 105. I recommend checking that out if you struggle with this problem very quickly the time complexity of this solution the way I'm doing it the time complexity of this solution is Big O of N squared at least the simple way and you can make an optimization which makes it Big O of n I'll show you both code Solutions because it makes sense going from N squared to Big O of n let's do that right now so as we try to build the tree we know the root node is the easy part we just take our post order and pop the last value from it and that's how we can create our root notes so I'm going to create a node tree node Constructor passing in that value and we're going to call this our root value then we want to know the index that this appears in in the in order array so we're going to say in order dot index of this value which is root dot value so let's call this the index and then we want to start building the subtrees we want to start with the right subtree and we're going to assign that to root dot right so how do we build that let's recursively call Self dot build tree the only thing is now the parameters are going to be different well post order is going to be the same it's pretty simple so we're just going to pass in post order we're always going to pop from the end of our post order array but in order matters it could be empty it could be null so we're going to take in order and basically slice it we want the right portion everything to the right of this index so we're going to say start at index plus 1 and then go up until the end of that array similarly when we build the left subtree we're going to do it just like this except assigning it to root dot left and we want everything to the left of this index so we're going to start at the beginning of the in order array and go up until the index but not including the index in Python that's exactly what this will do this is non-inclusive so with this we're building the two subtrees the only thing is what's our base case at what point will we return null well if we don't have any nodes to the left of that index or to the right of it that's how we're going to return null how are we going to know if that's the case well this in order array that we're slicing if it ever is null we pass in null which would happen if not in order then we're going to return null after we build the tree we just just want to return the root so if I run this code it will work even though it's not the most optimal solution so let's try to improve this this is N squared because of two reasons we're having to find the index of a value in an array that means we're linearly scanning through the in order array and the second reason is we're creating a sub array when we don't necessarily need to so let's improve this this part is the easy part why should we have to scan through the array when we could just pre-do that work we could pre-compute it using a hash map so I'm going to create a hash map called in order index in Python it's pretty easy I'm going to say for i v in enumerate the in order array and I'm going to have the value be the key and mapping that to the index so every value in the in order array is going to be mapped to some index that's pretty much what this is doing if you're not familiar with python this is just a concise way to write it but you could you know write out the entire for Loop but this is pretty simple what this is doing here now instead of having to scan through the array we can use this hash map so I'm going to copy and paste it use this hash map and then use the root dot value as the key and that will give us the index and we don't have to scan through the array this is an O of one operation now the second thing is we're having to pass in sub arrays we don't have to create these sub arrays because instead of passing them in we can just pass in the indexes that Define that subarray so to do that though we're going to need a different function header so I'm going to actually within this function create another function header which I'm going to call helper and instead of passing in the actual arrays themselves since we know post order isn't really changing we don't even have to pass that in as a parameter we just have to pass in the boundaries of the in order array the left and right boundaries of that array so now I'm just going to tab this and when we call our helper now we're going to be passing in 0 as the starting left index and the length of in order minus 1 as the right index and we're going to return the result of this which will be the root node but just a couple more things we have to change here now here instead of calling self.buildtree we're going to call this helper function make sure to remember to do that I forgot to which is what caused me a few bugs so updating that and the parameters here that we're going to be passing in instead of passing in the arrays we want to pass in the boundaries so everything to the right of this index well given these boundaries left and right we want everything to the right of this index we're going to say index Plus 1 is going to be the left boundary and the right boundary is going to remain unchanged now for the left subtree we want everything to the left of this index so we're going to have our left index remain unchanged because that's the leftmost index and our right index is going to be index minus 1. we want everything to the left of this value now there's just one last thing to change the base case how do we know now if the in order portion of the array is empty because that's the base case clearly here but we're not passing in the in order sub array here anymore so how do we know if it's empty well we would know if the left pointer crosses the right pointer like for example if the left and right indices were equal then we have this index and then here we call index plus one well then index plus 1 is going to be greater than this value that would happen when we reached the case where the left and right indices are equal so if the left pointer crosses the right pointer which means that left is greater than right then we're going to return null so now the code is pretty much complete let's run it to make sure that it works and as you can see it does and it's definitely more efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon