Now.
Previously, we have discussed how we can implement this in a recursive manner, and when we do it in
that way, we are using the recursive call stack.
But over here, because we are trying to implement the iterative solution, we are going to just use
a normal stack for it.
All right.
And again remember we have discussed previously that a stack is a data structure or a last in first
out data structure.
So if you have a stack over here and let's say you add the value one, then you add the value two.
And then if you're trying to remove from the stack, the last value that came into it will be the first
value to come out of it.
So that's why it's last in first out.
And we will use this property of a stack to implement the iterative solution for preorder traversal
of a binary tree.
So let's discuss how we can do this.
So we start with the root node.
And let me add that to a stack.
So I have a stack over here.
And I have added the root node to the stack.
And again remember it's not the value it's the node that I'm adding to the stack.
Now I'm going to have a while loop.
And this is going to repeat as long as something is there in the stack.
And at this point we see that we do have something in the stack.
So we enter the while loop.
So what we'll do over here is first we will pop from the stack.
And then we will add the value of the node that was popped from the stack to an array.
Let's call it the results array.
So if you call this the results array, we're going to add the value of this particular node that was
popped to the results array.
So at this point we are popping this node and it has the value one.
So we add one to the results array.
Again I'm just showing it over here.
Initially the results array is empty.
And at this point it will just have the value one.
Now we will first add the right child of this particular node to the stack.
And again it's of course only if it does have a right child.
And then we will add the left child of the particular node to the stack.
Now this order is important because for the preorder traversal we have root.
And then we have left.
And then we have right.
So we have to visit the left node before visiting the right node.
And we are adding the right child first before adding the left child.
Because let's say I've added the right child that's at this point over here.
And then I am adding the left child.
Now because a stack is a data structure.
When I pop from this, I'm going to get left before right?
And that is something which is important for preorder traversal.
So I have to get the left node before the right node.
And that's why we will add the right node first.
And then we will add the left node.
And this is of course only if the node at hand does have a right and left child.
So this is how we're going to approach this.
So let's see.
And just let's trace the algorithm and see what's going to happen.
So at this point we have node one.
And you can see that it does have a left child and a right child.
So first I'm going to add the right child which has the value three.
So the node three is going to get added to the stack.
And then the left child which is this node over here which is two will be added to the stack.
And again all of these are nodes because later once we pop this we'll need to check whether that particular
node has a left or right child.
And if we were to just add values to the stack, we would not be able to do that.
So that's why we have to keep adding nodes to the stack.
All right.
So we have two and three in the stack.
And then we see that the stack is not empty.
So therefore we come over here and we are going to pop from the stack.
And again we're going to pop from the top because a stack is a data structure.
So we pop the node two and we're going to add the value of this particular node which is two to the
results array.
And then we're going to check whether this node has a right child.
And we can see that it does have a right child.
So we're going to add this node to the stack.
So we have five added over here.
And then we also add the left child which is four.
So we have four and five over here.
And the stack is not empty.
So we pop from the stack and we add the value of four to the results array.
And we see that this particular node does not have a left or right child.
So we proceed.
And at this point again the stack is not empty.
So we come over here and we're going to pop from the stack.
And we'll add the value five to the results array.
And this node over here does have a left child.
So we're going to add that child over here.
Again notice it does not have a right child.
So we can't add anything for this line of code.
But over here we see that it does have a left child.
So we add the node seven to the stack.
And then we come again.
Over here, we see that the stack is not empty.
Therefore, we are going to pop from the stack and we'll add the value to the results array.
And this node over here does not have a left or right child.
So nothing gets added to the stack.
And we again come over here.
The stack is not empty.
So we pop from the stack and we add the value to the results array.
And at this point we check whether this node has a right child.
It does have a right child.
So we add this to the stack and it does not have a left child.
So only node six gets added to the stack.
And we are again over here we see that the stack is not empty.
So we pop from the stack.
We add the value to the results array.
And this node over here does not have a right child, but it does have a left child.
So it gets added to the stack.
And again we are over here.
The stack is not empty.
So we pop from the stack and we add the value to the results array.
Again we come over here and at this point the stack is empty.
So we are done.
And notice that we have got the preorder traversal of the binary tree.
And we have implemented this with this stack.
And thus this is the iterative way for implementing the preorder traversal of a binary tree.