Welcome back.
Let's do this question.
Given the root of a binary tree, return the inorder traversal of its nodes values.
Write the iterative solution okay, so we are asked to implement a function which will spit out the
inorder traversal of the given binary tree.
And again notice this array over here does not consist of nodes, but rather just consists of the values
of the respective nodes.
So we are given an example over here.
If this is the binary tree which is given to us, this is the expected output.
And notice that this is the postorder traversal of this binary tree, where first we go left, then
we go right, and then we visit the root node.
So let's quickly take a look at this example over here.
So we start at the root node.
Then we go left because we first have to go left.
So we come over here and this becomes the root node.
But then before we process this node we have to go again left because there is a node over here.
So we reach over here and then we try to go left.
So there's nothing on the left.
And then we try to go to the right.
There's nothing on the right.
And then we process the root node which at this point is this node over here.
So that's how we get the value for over here.
And then we come over here we're done with the left part.
And notice after left we have to go to the right.
So before we process this node over here we come to the right.
And this becomes the root node.
And then before we process this node we have to go left.
So we come over here okay.
And then we try to go left.
There's nothing on the left.
And we try to go to the right.
There's nothing on the right.
And we process the root node at this instance which is this node over here.
So that's how you get seven over here.
And then we come over here we try to go right.
There's nothing on the right.
So then we come over here which is the root node.
So you get five over here okay.
So notice at this point for this subtree over here we are done with the left part and we are done with
the right part.
Therefore now we visit the root node which is two for this subtree over here.
And that's how we get two over here.
And then we come over here okay.
So this is the root node at this point.
And we are done visiting the left part of this node.
Now before we process this node over here we have to go to the right.
So we come over here and before we process this node which is the root at this point we try to go to
the left but there's nothing on the left.
And then we try to go to the right.
So we come over here and before we process this node we again go left.
So we come over here.
Now we again try to go left but there's nothing on the left.
We try to go to the right.
There's nothing on the right.
And then we process this node which is the root at this point.
So that's how you get eight over here.
And then we come back over here.
So we are done with the left part.
We try to go to the right but there's nothing over here.
And therefore we go ahead and process the root node which is six.
So we get six over here.
And then we're done with this.
So we come over here.
So we did try to go to the left but there was nothing on the left.
And then we did process the right part as well.
So therefore now we go ahead and process this node over here which is the root node for this subtree.
So you get three over here.
And at this point we come over here.
Notice that we're done processing the left part of this node as well as the right part of this node.
And therefore we go ahead and process the root node which is one.
And therefore we get one over here.
So that's why this is the postorder traversal of this binary tree over here.
In the next video, let's try to think how we can solve this question in an iterative manner.