1
00:00:00,690 --> 00:00:07,740
In the previous video, we have discussed how to implement the postorder traversal for a given binary

2
00:00:07,740 --> 00:00:09,900
tree in an iterative manner.

3
00:00:09,930 --> 00:00:16,320
In this video, let's think about the time and space complexity of the approach that we came up with.

4
00:00:16,320 --> 00:00:23,190
So when it comes to the time complexity, it's going to be of the order of n, where n is the number

5
00:00:23,190 --> 00:00:25,350
of nodes in the given binary tree.

6
00:00:25,350 --> 00:00:29,970
And this is because we will be visiting each node one time.

7
00:00:30,330 --> 00:00:34,320
And this is what we try to do when we try to traverse a given binary tree.

8
00:00:34,350 --> 00:00:41,400
Now when it comes to the space complexity, it's going to be of the order of the height of the binary

9
00:00:41,400 --> 00:00:41,730
tree.

10
00:00:41,730 --> 00:00:48,540
So I can say the space complexity is of the order of H, where h represents the height of the given

11
00:00:48,540 --> 00:00:49,290
binary tree.

12
00:00:49,320 --> 00:00:53,820
Now again, let's take a look at the worst case for the space complexity.

13
00:00:53,820 --> 00:00:59,190
Let's say we are given a binary tree which is unbalanced, which looks something like this.

14
00:00:59,190 --> 00:01:05,640
Okay, now over here initially we would add the root node which is one to the stack.

15
00:01:05,640 --> 00:01:09,330
And we would add its child which is this node over here to the stack.

16
00:01:09,330 --> 00:01:12,210
So the stack would have two nodes at this point.

17
00:01:12,210 --> 00:01:15,870
And then we would pop two from the stack over here.

18
00:01:15,870 --> 00:01:21,900
And then as we have discussed in the previous video, we would again add two to the stack.

19
00:01:21,900 --> 00:01:24,180
And at this point it would be a root node.

20
00:01:24,180 --> 00:01:27,060
And we would also add its children to the stack.

21
00:01:27,060 --> 00:01:29,970
So the stack at this point would look like this.

22
00:01:29,970 --> 00:01:33,210
So notice that we have three nodes in the stack.

23
00:01:33,210 --> 00:01:41,100
And that's why the worst case space complexity for this solution is going to be of the order of n.

24
00:01:41,100 --> 00:01:45,990
And that happens when we are dealing with an unbalanced binary tree okay.

25
00:01:45,990 --> 00:01:52,380
So in the case of an unbalanced binary tree, it could be the case that H which is the height of the

26
00:01:52,380 --> 00:01:58,770
binary tree is equal to n, where n represents the number of nodes in the given binary tree.

27
00:01:58,770 --> 00:02:04,260
So the worst case space complexity of this solution is going to be of the order of n.

28
00:02:04,260 --> 00:02:08,190
Now, if we are dealing with a balanced binary tree.

29
00:02:08,400 --> 00:02:10,350
And let's take an example for that.

30
00:02:10,350 --> 00:02:15,420
So let's try to think of what would be the space complexity in this scenario.

31
00:02:15,420 --> 00:02:21,360
So over here initially we would be adding one the node with the value one to the stack.

32
00:02:21,360 --> 00:02:24,390
And we will also be adding its children two and three.

33
00:02:24,390 --> 00:02:24,720
Okay.

34
00:02:24,720 --> 00:02:27,060
So this is how the stack would look like.

35
00:02:27,060 --> 00:02:30,090
And then we would pop two from this stack.

36
00:02:30,090 --> 00:02:32,910
And we would again add two to the stack.

37
00:02:32,910 --> 00:02:35,310
And at this point two would be the root node.

38
00:02:35,310 --> 00:02:38,280
And we would add its children which is four and five.

39
00:02:38,280 --> 00:02:41,190
So the stack at this point would look like this.

40
00:02:41,190 --> 00:02:47,790
Now for this approach that we have discussed the best case scenario, which is the case where the binary

41
00:02:47,790 --> 00:02:50,070
tree which is given to us is balanced.

42
00:02:50,070 --> 00:02:55,110
We know that the height of a balanced binary tree is equal to log n.

43
00:02:55,110 --> 00:02:57,420
So we can say that h is equal to log n.

44
00:02:57,420 --> 00:03:00,660
When the binary tree which is given to us is balanced.

45
00:03:00,660 --> 00:03:07,920
Now, why can we say that the space complexity in this scenario is of the order of log n?

46
00:03:07,920 --> 00:03:09,900
Let's try to think about that now.

47
00:03:09,900 --> 00:03:17,460
We have seen clearly that it's not strictly equal to log n, because over here we have only seven nodes

48
00:03:17,460 --> 00:03:20,430
and log n would be less than three.

49
00:03:20,430 --> 00:03:24,330
But the space complexity used over here is more than that.

50
00:03:24,330 --> 00:03:30,420
But when we say that the space complexity is of the order of log n, and again I'm talking about the

51
00:03:30,420 --> 00:03:34,140
best case scenario where we are given a balanced binary tree.

52
00:03:34,140 --> 00:03:38,490
So in general we know that the space complexity is of the order of H.

53
00:03:38,490 --> 00:03:44,970
But in the case of a balanced binary tree, the space complexity is going to be of the order of log

54
00:03:44,970 --> 00:03:51,540
n, because the height of the binary tree determines the stack usage.

55
00:03:51,540 --> 00:03:57,270
Okay, we're not saying that it's going to be exactly equal to the height of the binary tree, but rather

56
00:03:57,270 --> 00:04:00,270
the height is what determines the stack usage.

57
00:04:00,270 --> 00:04:06,720
Because as you can see, what just happened in this example is that we are going down this branch.

58
00:04:06,720 --> 00:04:07,050
Okay.

59
00:04:07,050 --> 00:04:10,110
So we did remove this node and we added it back.

60
00:04:10,110 --> 00:04:11,520
So we have two again over here.

61
00:04:11,520 --> 00:04:13,830
And we added its children okay.

62
00:04:13,830 --> 00:04:20,790
So the height of the binary tree will determine how far we go down in this manner.

63
00:04:20,790 --> 00:04:25,920
So that's why the space complexity of this solution is of the order of H.

64
00:04:25,920 --> 00:04:31,680
Even though we can have nodes from right branches as well, which is what we have seen over here.

65
00:04:31,680 --> 00:04:34,920
For example, we have this node over here in this stack.

66
00:04:34,920 --> 00:04:35,970
But that's okay.

67
00:04:35,970 --> 00:04:42,210
All that we mean when we say that the space complexity is of the order of H, it means that the height

68
00:04:42,210 --> 00:04:44,700
is what determines the stack usage.

69
00:04:44,700 --> 00:04:49,380
Even though there can be a few more nodes in the stack at a particular point.

70
00:04:49,380 --> 00:04:56,310
So the space complexity of this solution is of the order of H, where h is the height of the tree,

71
00:04:56,310 --> 00:05:00,240
and we have seen that in the worst case the space complexity is going.

72
00:05:00,350 --> 00:05:06,980
Going to be of the order of N, and in the best case, which is a balanced binary tree, the space complexity

73
00:05:06,980 --> 00:05:09,110
is going to be of the order of log.