1
00:00:00,200 --> 00:00:05,870
Let's now take a look at the space and time complexity for the approach that we came up with in the

2
00:00:05,870 --> 00:00:11,420
previous video, where we implemented in-order traversal in an iterative manner.

3
00:00:11,450 --> 00:00:18,170
Now the time complexity is going to be of the order of n, where n is the number of nodes in the given

4
00:00:18,170 --> 00:00:19,010
binary tree.

5
00:00:19,010 --> 00:00:22,730
And that's the case because we will be visiting every node one time.

6
00:00:22,850 --> 00:00:30,110
Now, when it comes to the space complexity, it's going to be of the order of n, because in the worst

7
00:00:30,110 --> 00:00:35,960
case, if we have a tree that looks like this, which is a skewed binary tree, we would have to add

8
00:00:35,960 --> 00:00:38,000
all of these values to the stack.

9
00:00:38,000 --> 00:00:43,790
So that's why in the worst case, the space complexity is going to be of the order of n.