N-ary Tree Postorder Traversal - Leetcode 590 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Nary tree post order traversal so the idea is basically if you know what a regular tree is well when I say regular I mean binary that's kind of the most common where each node will have at most two children so something like this well we could relax that constraint of having two children and allow multiple children so zero children one children two and then more than that so 3 four five it could be unbounded so what kind of data structure do you think we should use to store all of the children of a particular node well we can't just have one or two variables for that anymore so now we probably need something like an array and that's exactly what we're going to have in most languages we're going to have like a resizable list as the children variable for a node object now so imagine you have multiple children for a node well now how do you do the postorder traversal remember post order traversal just means you will only visit a node after all of its children have been visited and that's going to be recursive so that applies for all of these nodes as well so basically we're going to do all of the descendants of a single node and then we'll pop back up to the parent and then do all the other descendants of that node and then we'll do the parent recursively with two nodes with postorder reversal what we would do is do the left child then recursively do the right child and then lastly do the current node so the only thing that's going to change from here to the general tree is that these two steps are actually going to be merged into a single step and that's going to be run a helper function or just recursively on the children all of them and I think the order does matter so we probably want to do the leftmost child first and then the next one and then the next one so do that and then lastly or the second step really is just the original node so it's pretty much the same recursively I'll also do this iteratively for you as well the time and space complexity I think is going to be the same but let's solve this this recursively now so I'm going to create the helper function down here and that's what I'm going to call it we're going to be given a current node the base case is the same as like pretty much every recursive tree problem so if not node then just return there's no need to return anything because what we want to do is basically collect all the values of every node and then put them in a list and then return that so from here we could return an empty list from here and then do a bunch of joining with the recursive call but I think it's probably just easier to have like a variable like this result and then we can just return that out here and then within the function we can modify that we could have made it a member variable if we needed to but I didn't so here remember there's two steps we're going to go through every child so for a child in node. that is the data type that's given to us I think it should be a list type but in Python it's kind of ambiguous and then so for all the children we're going to run the helper function recursively on them and then after that's done to the result we want to append the current nodes value so node do value with this problem I think we could have just gotten the return values from here and then joined them into a single list but that wouldn't have been as efficient and it would have been more complicated to code that up as well so this is I think the working solution let's run it okay well I promise you it would be the working solution if we didn't forget to actually call the helper function so let me do that on the root really sorry about that okay there you go it works this is technically the most efficient solution we're just going to go through every node in the tree so in terms of the uh time complexity would have been Big O of n in terms of the memory complexity it still would have been Big O of H where H is the height of the tree for a balanced tree it should be log n it should be log where the base is I guess the branching Factor if that's the correct term for this but anyways let's now do the iterative solution actually and I'll quickly walk you through how we're going to do it the time and space complexity though is going to be the same I just think it's interesting to solve this iteratively sometimes that can be asked in interviews so let's do it so we kind of just talked about how to do this recursively well doing it iteratively isn't too much different it's definitely not much different from just doing it on a regular binary tree but let's still imagine we have multiple children we have three children let's say so here we want to do this guy so if we were doing this iteratively usually we have a stack and that's what we're going to have this time but I'll just kind of spoil this for you this is in most languages going to require two stacks one stack where we actually add the node itself and then another stack where we Mark if that node has been visited or not that's going to be with a Boolean value and the reason for that is imagine we were just doing this pre-order style or even if we're doing this in order pre-order would be pretty easy that would mean taking this node visiting it and then we want to go through all of the children well that's what we're going to need the stack for because for us to say okay we go through all the children first we want to go to this child and then do all of its descendants and then eventually we want to come back here so that's what the stack would be for we wouldn't add this to the stack we would add these guys to the stack in that order well maybe this time it would be in reverse order because we'll pop the last thing that was added to the stack that would be pre-order in order would be pretty similar as well except that time we would add this to the stack and then go left and then eventually we'd pop back here and then we'd go right well with postorder it's a little bit unique I think post order is the hardest one to do even with just a regular binary tree and that's because when we get to this node we want to actually do this node last so how do we do that well we add this to the stack and then we go through its children okay but if you try that then you're going to go through the children you're going to end up adding let's say this guy also to the stack and then when you pop this from the stack there's no guarantee that all of its descendants has been like visited because we're going to be adding these guys first and then adding The Descendants since we're popping first in first out these are going to be popped before their children are popped so that's why we're going to have two stacks sometimes we're going to pop a node and it hasn't been visited before that's fine but once a node has already been visited and it's being visited for the second time that's when we know we're actually finished with that node so just to quickly dry run this I'll give some numbers to these nodes initially we're going to have uh the node one and we're going to say it hasn't been visited so it's false that's what we're going to pop first and then we're going to see that it was not already visited so this time we're going to add it back to the stack and this time we're going to mark it visited and we're going to take its children and then add them to the stack now too we're probably going to do it in reverse order so we'd do this four three I'm running out of space sorry and then two and then these would all be false and then we'd pop this one most recently that's why we added it last because it's two that's the one that we' want to go through first so we'd pop this we'd see this hasn't been visited yet either so we'd add it back to the stack and we'd add its children and you can continue with this eventually we'll have gone through all of these and then we'll get to this guy and this will be the last one that we pop this is the last item in our stack so it makes sense that it is the root of our tree so that's the idea let's go ahead and code this up okay so I'll actually leave this code here because I'm pretty sure my solution will be pretty similar so here I'm going to start the stack like this with just the root and we're going to say false it hasn't been visited yet and it's actually technically possible that the root could be null so my code isn't really going to handle that elegantly so I think the best way to handle that is just with an if statement so if not root go ahead and return an empty list otherwise let's go through the stack while stack we're going to pop so pop from this stack and we're going to get two values by the way in Python I am using a tuple a pair of values you could probably do that in other Lang as well that have like a pair class but if you wanted to you could also just have two separate Stacks they're always going to be of the same length anyway so that works too so we pop we get two things we get the node and we get if it's been visited or not if it's not been visited this is what we do or actually if it has already been visited that means this is the second time we're seeing it so then we're just going to take its value and append it to the result so result do append node. Val and you can see that this is actually analogous to what we did in the recursive solution down here technically the first time we see this node is when we start the recursive call and we check if it's null we return immediately then we go through all of its children and then we come back in the second time we see that same node that's when we actually append it to the result after we've gone through the children so that's what we're doing up here as well so we have one case where it was visited and we have the other case where it's not been visited so we're going to add it back to the stack so a stack. append this node but this time Market as visited so first it was false now it's going to be true and go through all of the children for C in node. children add them to the stack as well so see and mark them as false they haven't been visited this is the first time they're being added to the stack and then after all of this we can just return the result there's only one problem with this and remember it's the order the order that we add the children in does matter so I think in this case we want to do it in reverse order in Python that's pretty easy easy to fix here we can just add colon colon minus one this basically goes through the list in reverse order I think we're good here let's go ahead and run this and as you can see it works it's pretty efficient this is the iterative solution the time and space complexity I believe is the same if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon