In the previous video, we have discussed how to implement the postorder traversal for a given binary
tree in an iterative manner.
In this video, let's think about the time and space complexity of the approach that we came up with.
So when it comes to the time complexity, it's going to be of the order of n, where n is the number
of nodes in the given binary tree.
And this is because we will be visiting each node one time.
And this is what we try to do when we try to traverse a given binary tree.
Now when it comes to the space complexity, it's going to be of the order of the height of the binary
tree.
So I can say the space complexity is of the order of H, where h represents the height of the given
binary tree.
Now again, let's take a look at the worst case for the space complexity.
Let's say we are given a binary tree which is unbalanced, which looks something like this.
Okay, now over here initially we would add the root node which is one to the stack.
And we would add its child which is this node over here to the stack.
So the stack would have two nodes at this point.
And then we would pop two from the stack over here.
And then as we have discussed in the previous video, we would again add two to the stack.
And at this point it would be a root node.
And we would also add its children to the stack.
So the stack at this point would look like this.
So notice that we have three nodes in the stack.
And that's why the worst case space complexity for this solution is going to be of the order of n.
And that happens when we are dealing with an unbalanced binary tree okay.
So in the case of an unbalanced binary tree, it could be the case that H which is the height of the
binary tree is equal to n, where n represents the number of nodes in the given binary tree.
So the worst case space complexity of this solution is going to be of the order of n.
Now, if we are dealing with a balanced binary tree.
And let's take an example for that.
So let's try to think of what would be the space complexity in this scenario.
So over here initially we would be adding one the node with the value one to the stack.
And we will also be adding its children two and three.
Okay.
So this is how the stack would look like.
And then we would pop two from this stack.
And we would again add two to the stack.
And at this point two would be the root node.
And we would add its children which is four and five.
So the stack at this point would look like this.
Now for this approach that we have discussed the best case scenario, which is the case where the binary
tree which is given to us is balanced.
We know that the height of a balanced binary tree is equal to log n.
So we can say that h is equal to log n.
When the binary tree which is given to us is balanced.
Now, why can we say that the space complexity in this scenario is of the order of log n?
Let's try to think about that now.
We have seen clearly that it's not strictly equal to log n, because over here we have only seven nodes
and log n would be less than three.
But the space complexity used over here is more than that.
But when we say that the space complexity is of the order of log n, and again I'm talking about the
best case scenario where we are given a balanced binary tree.
So in general we know that the space complexity is of the order of H.
But in the case of a balanced binary tree, the space complexity is going to be of the order of log
n, because the height of the binary tree determines the stack usage.
Okay, we're not saying that it's going to be exactly equal to the height of the binary tree, but rather
the height is what determines the stack usage.
Because as you can see, what just happened in this example is that we are going down this branch.
Okay.
So we did remove this node and we added it back.
So we have two again over here.
And we added its children okay.
So the height of the binary tree will determine how far we go down in this manner.
So that's why the space complexity of this solution is of the order of H.
Even though we can have nodes from right branches as well, which is what we have seen over here.
For example, we have this node over here in this stack.
But that's okay.
All that we mean when we say that the space complexity is of the order of H, it means that the height
is what determines the stack usage.
Even though there can be a few more nodes in the stack at a particular point.
So the space complexity of this solution is of the order of H, where h is the height of the tree,
and we have seen that in the worst case the space complexity is going.
Going to be of the order of N, and in the best case, which is a balanced binary tree, the space complexity
is going to be of the order of log.