So today, let's solve the problem, n-ary 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 three, 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 post-order 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 post-order traversal, 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 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 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 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.children, 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 node's value, so node.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 time complexity, it 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'll 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 post-order, 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, and 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 have been 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 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 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'd 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 languages 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.appendNode.value.

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 and 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 mark it 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 c 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 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 neatcode.io for a lot more.

Thanks for watching and I'll see you soon.