Between the in order, post order and preorder iterative functions.
The most difficult one is typically the post order.
And that's what we are trying to do over here.
So first let's start to build the necessary intuition to come up with the solution by making a few interesting
observations.
So as with the preorder and in order iterative solutions over here also we are going to use a stack
okay.
And first let's take an example.
Let's say this is the binary tree which is given to us which is a very simple binary tree.
And we start at the root node.
And in postorder traversal we know that we first go to the left part, then the right part, and finally
process the root node.
So for this simple binary tree over here, the necessary output would be two, three and one because
we first go left.
So we get two over here.
Then we go to the right.
So we get three over here.
And finally we process the root node which is one.
Now how would we get this order from the stack.
Because we know that a stack is a leaf or data structure.
Last in first out.
So we need this two to be the node that enters into the stack as the last node.
Okay.
And the first one to enter the stack has to be this node over here so that we get it out the last.
So this has to be the first one that enters the stack.
So that means that first we'll have to fill one into the stack.
And then three and then two okay.
So to generalize we can say that when we are at a root node first we are going to add the root node
to the stack.
And then we will add the right child to the stack, which is three over here.
And after that we're going to add the left child to the stack.
So this is the first observation that we can make.
So let's note it down.
Add the root node first to the stack.
Then add the right node.
And then add the left node.
And we have seen the reason for this.
In this example.
Let's now continue and make another interesting observation for this.
Let's take another example.
Let's say this is the binary tree which is given to us.
And in this case the expected output would be two, four, three and one.
Because first we go to the left.
And then when we come over here we try to go to the left, but there's nothing over here.
So we go to the right.
So we get four over here.
And then we process the root node which is three.
And finally for this node over here, we are done processing the left part as well as the right part.
And therefore we go ahead and process the root node which is one over here.
So for this binary tree over here the expected output is 243 and one.
Now let's draw our stack over here and make an interesting observation.
So first we start at the root node.
And based on what we have over here we are going to add one to the stack.
And then we'll add three.
And then we will add two okay.
So these three nodes are added to the stack.
Now imagine that we have a while loop that keeps repeating as long as there is something in the stack.
And at this point we see that the stack is not empty.
Now we will see more of this in the latter part of this video, but over here let's just work with this.
So at this point the stack is not empty.
So I pop from the stack and I get two, and I add the value of two to the array over here.
So I have this two over here okay.
Now I continue and I'm going to pop again from the stack.
So I get this three over here.
But notice I cannot add this three to the results array because for the postorder traversal I have to
go first left then right, and then only process the root node.
And over here if I get this three notice that I have not yet processed its left or right children,
so I cannot pop from this and add three to the results array.
Now this is an interesting time to make an observation.
As per what we have discussed so far, a node will get added to the stack in two ways one if it's a
root node.
For example, we added this one over here, which was a root node, or because a node is the left or
right child of a node, for example, two and three were added over here because three is the right
child and two is the left child.
So there are these two ways in which nodes get added to the stack.
Now, if I pop from this stack over here, and if I get a node which was added to the stack when it
was a root node, then I can be sure that its left and right children are already processed.
Now why is that the case?
Because node is over here.
First we add the root node.
Now if I were to draw it in the stack.
So first I add the root node and then it says that we add the right node.
And then we add the left node.
Okay.
So before I get to this node over here, which is a node that was added because it was a root node,
I will have processed already its left and right children, and therefore it follows the Postorder traversal
rule.
And therefore in this case it's okay to add it to the results array, which is something that we did
for two in this case.
Okay.
But if a node was added to the stack because it was the left child or the right child of a particular
node, and let's say I'm popping from the stack, as was the case when I popped from the stack and I
got this node over here, which has the value three, I cannot add it to the results array because I
would not have processed its left or right child.
Okay, so this is an interesting observation to make.
So what we have seen is that there are two possible ways in which nodes can get added to the stack.
The first way is as a root node, and the second way is as a left or right child.
Now if we pop from the stack and if we get a node that was added to the stack as a root node, we are
sure that its left and right children are already processed, and therefore we can go ahead and add
its value to the results array.
But if you are getting a node which was added to the stack because it was a left or right child, then
we cannot add its value to the results array because this particular node's left and right children
are not yet processed.
Okay, so that's what we have seen over here.
And because of this, we will need to be able to differentiate between these two types of nodes that
get added to the stack over here.
Okay.
And for this we will use another stack over here.
Let's just call it visited okay.
Now let's make some space over here and see how this plays out.
So we will use the same example.
So we have this binary tree over here.
And let's say we start with the root node filled in the stack okay.
So we have this node over here.
And then we are going to have a while loop that will keep looping as long as the stack is not empty.
Now at this point we will fill false in the visited stack over here.
Because notice that we just filled the root node to the stack to start with, and we have not yet processed
its left and right children.
Okay, so this is the starting point.
So what you've discussed is we are going to have a while loop that will keep looping as long as the
stack over here is not empty.
And we start with filling the root node to the stack over here and over here.
The value at this point, which corresponds to this node over here, is false, because we have not
processed or we have not added the left and right children of this particular node to the stack over
here.
Now let's get started.
What we are going to do is we are going to pop from the stack and the visited stack from these two inside
the while loop.
Okay.
So I'm going to pop from this and this.
So let me use two variables cur and visit or wish okay.
So Cur is going to equal stack dot pop.
So I get this node to equal to cur.
And this at this point is going to equal false okay.
So cur is one and this is false.
And then I'm going to check if cur is not null.
And if visited is true.
That would mean that this particular node was added to the stack when it was a root node.
Because for only root nodes added to the stack will make visitor true.
So at this point we see that visited is false.
So we come to the else part okay.
So if it was true then we would have added that value to the results array which is what we have discussed
over here okay.
But at this point, because we have false over here, we come to the else part because this at this
point is not truthy.
So we come to the else part.
And over here we are going to do three things.
We are going to append this particular node to the stack.
And at this point we're going to set visited to true because now cur is the root node okay.
So we're going to append this particular node Cur to the stack.
And we're going to append first its right child and then its left child to the stack.
So let's do that over here.
So I can append one and three and two to the stack over here.
Now when we append cur we are going to append true to the visited array, because now cur is a root
node.
And for the right and left children we are going to append false to the visited array because those
two are not root nodes.
Okay, so that's what we have seen.
So whenever a root node is added to the stack will have true which is the case over here.
And for nodes added to the stack because they are either a right child or a left child.
For those scenarios we're going to have false in the visited stack over here because again, we have
seen that for these nodes, we have not yet added their left and right children to the stack.
Okay.
So let's continue.
Now we see that the stack is not empty.
So again we come over here.
We're going to pop from the stack and from the visited stack over here.
And when we do that we get two and false.
So cur is two and at this point is again false.
So we come over here we have a node at cur.
But visited is false.
So we come over here and we're going to append this node to the stack.
Okay.
And we're going to have true in the visited array over here.
And then if it did have right or left children, we would have appended it to the stack.
But it does not have that.
Right.
So two over here as we see does not have any children.
So again we come over here and we see that the stack is not empty.
So we're going to pop from the stack.
And at this point CR is two.
And this is truthy or true okay.
So therefore we come over here and we're going to add the value of this node to the results array which
is what we have over here.
We proceed and we see that the stack is not empty.
So we're again going to pop from the stack and curries three and WIS at this point is false.
And therefore we come over here because this is not truthy.
So we come over here and we're going to append the node with value three to the stack and its right
child, which has a value four to the stack.
Now when we append three over here, the corresponding value is true because this node at this point
is cur right.
So we have seen that for cur, the corresponding value in the visited stack is going to be true, and
for its children it's going to be false.
So that's why we have false over here.
And this is the node with value four which is the right child of this particular node.
Over here again we proceed.
We see that the stack is not empty.
So we're going to pop from the stack and we get four and false.
So again we come to the else part because cur is a node.
But at this point this is false.
So we come to the else part and we're going to append this node to the stack.
And the corresponding value in visited is going to be true okay.
And there are no children for this particular node.
So that's it.
So again we come over here we see that the stack is not empty.
And therefore we come inside this and we're going to pop from the stack.
We get four.
And this at this point is true.
So cur is a node.
And this is true.
So we come over here and we're going to add the value of this particular node which is four to the results
array over here okay.
So we continue.
We again come over here.
We see that the stack is not empty because we have this node over here and this node.
So we're going to pop from the stack.
So cur becomes the node with the value three.
And this is true.
So cur is a valid node.
And this is true.
So we come over here and we are going to append the value of this particular node to the results array
which is this three over here okay.
And we continue.
We again come over here.
We see that the stack is not empty.
So we're going to pop from the stack.
And cur becomes the node with value one.
And this at this point is true because that's what we had over here.
And we see that Cur is a valid node.
And this at this point is true.
Okay.
So we come over here and we're going to append the value of this particular node to the results array
which is this one over here.
So this is how we will be able to traverse the given binary tree in a postorder manner.
And notice that this solution is an iterative solution.