So in this question, we are asked to implement in-order traversal for a given binary tree, and we
have to implement the solution in an iterative manner.
Now to start with, let's make a few observations to build the necessary intuition to come up with an
approach for this.
Now, previously when we had discussed inorder traversal in a recursive manner, we had used the recursive
call stack.
But over here, because we are doing it in an iterative manner, we are going to use a stack.
Okay.
So this is going to be the stack that we will be using.
And in the question it's mentioned that we are given the root of the binary tree.
So let's say that we assign the root to a variable called ker.
So ker at this point is pointing to this node over here which is the root node.
Now inorder traversal is about first visiting the left part, then the root and then the right.
So we have seen this previously.
So this is what we mean with inorder traversal.
Now let's continue making a few interesting observations.
So if we were to start over here and again we are given the expected output over here which is the inorder
traversal of this binary tree.
So how do we get this.
So we are starting at the root.
And then we have to go left.
And then we have to again go left.
So because that's what we have over here right.
So when we initially go left we will reach this node over here.
And this becomes the root.
But again at that particular instance we again have to first explore the left before going for the root.
So that's why we'll have to go again left.
And when we reach this node this becomes the root.
And we again have to try to go left.
But there is nothing over here.
Right.
So notice that we have to go left as much as possible.
So this is the first observation that we can make with respect to inorder traversal.
So we need to keep going left as much as possible.
And that's how we get this for over here in the results array.
The second observation that we can make is that once we have added four to the results array.
So we have tried to go left.
There's nothing over here.
Then this is the root.
So we add that over here.
And then we try to go right.
There's nothing over there.
And after that notice that for this subtree we are done exploring the left part.
And we would have to go back to two which at that point becomes the root.
So for this subtree we have explored the left part.
And now we need to add the value two to the results array which is the root.
So this is the second observation that we can make.
Once we are done exploring the left part we need to come back to the previous node, and we have to
do that before we go to the right part, because inorder traversal is all about going left first and
then exploring the root, and after that only going to the right part.
So we have made two interesting observations.
So we have come back over here and we have added the value two also to the results array.
And then we have to go right.
Right.
So that's how the inorder traversal would work.
So we go over here and when we come to five five becomes the root node.
And at this particular instance we have to explore the left part first before we add five to the results
array.
So we'll have to go again left as much as possible which is what we had over here.
Right.
So over here we have to come to the left again.
And when seven becomes the root node we again try to go to the left.
But we are not able to go to the left because there's nothing over here.
And then we add seven to the results array.
So this is how it works.
So the third observation that we can make over here is that after going right, which is what we did
over here, we again need to go left as much as possible.
Again, notice after we went right we again had to keep going left.
Now if we did have more nodes over here, we would have kept going left.
So these are three interesting observations that we have made.
Now let's see how we can use these three observations to come up with the pseudo code for implementing
inorder traversal in an iterative manner.
So the first thing is that we need to keep going left as much as possible.
So again at this point we have cur equal to the root node.
And then we are going to try to keep going left as much as possible.
So while cur points to a node we will append that node to the stack.
And then we will keep going left.
So again at this point we would append one the node one over here to the stack.
And then we'll go to two and we'll append two to the stack.
And then we'll go to four the node with value four.
And then we'll append the node four to the stack.
And.
We will again try to go left.
But at this point, because there's nothing on the left, we would come out of this while loop.
Now, once we are out of the while loop, notice what we did over here was we added this for to the
results array.
So for that we would have to pop from the stack and append the value of the node that we just now popped
to the results array.
So that's how we'll get four over here.
And after we are done with this, we will have to try to go to the right so we can say cur is equal
to the right node of cur.
And this is very important because inorder traversal is all about going first left, then exploring
the root node and then going right.
So we are done exploring the left over here because we went as much as possible to the left.
So we know that at this point where we are at node four, we are not able to go any further left.
So we are done exploring this part.
Then we pop this node over here from the stack and we added the value to the results array.
So over here we are done exploring the root node as well.
And then we have to go to the right.
So that's why we have to say cur is equal to cur dot.
Right okay.
So in this way we will be going to the right node of cur.
And we would have completed exploring the left, the root and the right part for this subtree, if at
all.
There was a subtree over here, right?
Even one node is a subtree.
But again, I'm just saying the case that if we had some nodes over here, we would have to go to this
part before we come back to two.
So that's it.
So at this point this is how our stack looks like.
And we have popped the node four from the stack.
And we have added it to the results array.
Another point to note over here is that we have to keep appending the node.
As we keep going left, we have to keep appending the node to the stack because we need to come back
later.
And before we go right, we have to visit the root node.
Right.
So that's why we have to keep adding the nodes that we visit to the stack.
All right.
Now the last step in the pseudocode for the inorder traversal implemented in an iterative manner would
be to have a while loop over here, and we will keep doing what we discussed over here as long as either
these two conditions is true.
That is, if the stack is not empty, we'll keep doing this.
Or if the cur.
The variable cur is pointing to a node, and if it's not none, we will keep doing this.
Now this is important because let's say we went to the right.
But as we've discussed over here, once we go to the right, we have to keep going left.
Like for example, we came over here and then we have to keep going left as much as possible.
And that would be achieved over here.
Right.
So again we went to the right over here.
And then when we come again to the beginning part of this loop, we would keep going left as much as
possible.
Another reason why we have to keep doing this as long as either of these two conditions is true, is
because we also need to come back and visit the root node, which is what we have done over here.
Right?
So once we're done with this part, we would have to come over here.
So that's why we have to keep doing this because this would be covered by the stack not being empty.
Now we have seen and we have developed a good intuition of how this works.
Now let's solidify our learning by just tracing the algorithm that we've written or the pseudocode that
we have written over here.
So initially Cur is pointing to this node and Cur is not none.
So it's pointing to an actual node.
But the stack is empty.
But this condition is true.
So we enter the while loop.
Now cur is pointing to this node and we will append it to the stack.
So we have the node one in the stack.
And then we go to the left.
So cur is now pointing to this node over here.
And again cur is pointing to a node.
So this is true.
So we again append this node to the stack.
And we go left.
And at this point, again Kurt is pointing to a node.
So we append this node to the stack.
And we try to go left.
And over here there's nothing.
So curb becomes none.
So we come out of this while loop and we come to this part.
Now we are going to pop this and we add the value of this node to the results array.
And then that's this part over here.
And then we are going to go to the right.
Right.
So over here this is cur at this point and we're trying to go to the right.
But again cur is none at this point because there's nothing over here as well.
Now when we come to this condition over here, we see that cur is none, but the stack is not empty,
right?
So it means that there are some nodes whose value has to be yet added to the results array.
So again we come over here and cur is none.
So we come over here and we're going to pop from the stack.
And we'll add the value two to the results array.
And we try to go to the right.
So this was cut at this point.
And we go to the right.
So cur becomes the node five.
And then when we come over here cur is pointing to a node.
And then we come over here and we see that car is not none.
So we append this node over here to the stack.
And we try to go to the left.
And yes, we can because there is a node over here.
So car at this point is pointing to this node over here.
And this is going to be appended to the stack.
And we go left, at which point car becomes none because there's nothing over here.
And we come out of this while loop.
And then over here we are going to pop from the stack and we'll add the value seven to the results array.
And that's over here.
And then we are going to the right.
So again we are trying to go to the right.
But there's nothing over here.
So car becomes none.
So at this point when we come to this condition car is none.
But the stack is not empty.
So again we enter the while loop and car is none.
So we skip this part and we come over here and we are going to pop from the stack.
And we add the value five to the results array.
And we try to move to the right.
And again there's nothing over here.
So car is still none.
And when we come over here car is none.
But the stack is not empty.
So again we enter the loop and we are going to pop from the stack and we add the value one to the results
array.
And then we say that car is car dot right.
So we go to the right.
So we come over here.
Now car is the node with value three.
And then when we come over here we see that car is pointing to a node.
So we append it to the stack and we go left.
So when we go left car becomes none.
And then we come over here we exit this while loop.
We come over here, we're going to pop from the stack, and we'll add the value three to the results
array.
And we try to go to the right.
And yes we have something over here.
So car becomes six.
And then over here we again come to this while loop over here we're going to append six to the stack.
And then over here we are going left.
We'll go left.
So car becomes eight and eight, gets added to the stack and then car becomes none.
So we come out of this while loop.
We pop from the stack which is this eight over here.
And the value eight gets added to the results array.
And we try to go to the right.
But again there's nothing over there.
So car is still none.
And we come over here.
Car is none.
So we come to this part.
We're going to pop from the stack which is this six over here.
And we add the value six to the results array.
At this point car is none and the stack is empty.
So this while loop also is exited.
And notice we were able to traverse the binary tree which was given to us using inorder traversal.
And we implemented this over here in an iterative manner.
In the next video, let's take a look at the space and time complexity of this approach.