1
00:00:00,580 --> 00:00:01,660
Welcome back.

2
00:00:01,870 --> 00:00:08,440
Let's now take a look at the time and space complexity for the iterative approach for implementing preorder

3
00:00:08,440 --> 00:00:10,600
traversal on a binary tree.

4
00:00:10,630 --> 00:00:17,170
Now, when it comes to the time complexity, this approach is going to be having a time complexity of

5
00:00:17,170 --> 00:00:24,670
the order of n, where n is the number of nodes in the given binary tree, because we will be visiting

6
00:00:24,670 --> 00:00:26,230
every node one time.

7
00:00:26,740 --> 00:00:28,840
What about the space complexity?

8
00:00:28,870 --> 00:00:36,190
The space complexity of this solution is going to be of the order of H, where h is the maximum height

9
00:00:36,190 --> 00:00:36,970
of the tree.

10
00:00:37,000 --> 00:00:38,590
Now why is that the case?

11
00:00:38,620 --> 00:00:46,990
Notice that in the worst case, for each level that we go down in the binary tree, we will be popping

12
00:00:46,990 --> 00:00:51,760
one node from the stack and we will be adding two nodes.

13
00:00:51,760 --> 00:00:56,050
The left and right child of the node that was popped to the stack.

14
00:00:56,050 --> 00:01:00,400
So net net we are going to remove one node and add two nodes.

15
00:01:00,400 --> 00:01:02,590
So that's adding one node.

16
00:01:02,590 --> 00:01:09,850
So for every level that we go down in the binary tree, in the worst case we will be adding one node

17
00:01:09,850 --> 00:01:10,690
to the stack.

18
00:01:10,690 --> 00:01:18,220
So that's why the space complexity or the maximum auxiliary space that will be used at any given point

19
00:01:18,220 --> 00:01:24,490
of time, will be of the order of H, where H is the maximum height of the binary tree.