1
00:00:00,360 --> 00:00:07,170
Let's now discuss the space and time complexity of the approach that we have discussed for solving path

2
00:00:07,170 --> 00:00:08,070
sum two.

3
00:00:08,100 --> 00:00:15,780
The space complexity of the solution that we came up with is of the order of H, where h is the maximum

4
00:00:15,780 --> 00:00:17,580
height of the binary tree.

5
00:00:17,610 --> 00:00:19,110
Now why is this the case?

6
00:00:19,110 --> 00:00:20,850
Let's try to think about that.

7
00:00:20,850 --> 00:00:25,590
Let's say the binary tree which is given to us has this structure.

8
00:00:25,620 --> 00:00:28,410
Now for the approach that we came up with.

9
00:00:28,410 --> 00:00:32,940
What are the things that take up auxiliary space or extra space?

10
00:00:32,940 --> 00:00:36,810
The things that take up extra space are the Cur array.

11
00:00:36,810 --> 00:00:40,740
And we will also be using space on the recursive call stack.

12
00:00:40,770 --> 00:00:47,640
Now notice over here in this path where we go from the root to the leaf, this is the case where cur

13
00:00:47,670 --> 00:00:52,200
would have the maximum number of values which is four okay.

14
00:00:52,200 --> 00:00:58,830
And in this case the recursive call stack will also take up space of the order of H, where h is the

15
00:00:58,830 --> 00:01:01,020
maximum height of the binary tree.

16
00:01:01,020 --> 00:01:06,870
So that's why we can say that the space complexity of this solution is of the order of H.

17
00:01:06,900 --> 00:01:12,870
Now notice that in the worst case, the space complexity will be of the order of n.

18
00:01:12,870 --> 00:01:14,460
Now why is that the case?

19
00:01:14,460 --> 00:01:17,190
Let's take another example to understand that.

20
00:01:17,220 --> 00:01:24,210
Now if the binary tree which is given to us is a skewed binary tree and it looks like this over here,

21
00:01:24,210 --> 00:01:32,070
notice that Cur would take up space of the order of n, and the space taken up on the recursive call

22
00:01:32,070 --> 00:01:34,770
stack will also be of the order of n.

23
00:01:34,770 --> 00:01:40,980
So that's why the worst case space complexity of this solution is of the order of n.

24
00:01:40,980 --> 00:01:48,090
Now, when it comes to their time complexity, the time complexity of this solution is of the order

25
00:01:48,090 --> 00:01:56,730
of n into h, where n is the number of nodes in the given binary tree, and h is the maximum height

26
00:01:56,730 --> 00:01:58,320
of the given binary tree.

27
00:01:58,350 --> 00:02:01,410
Now let's try to understand why this is the case.

28
00:02:01,410 --> 00:02:02,340
For this.

29
00:02:02,340 --> 00:02:09,510
Let's take an example where the binary tree which is given to us is a perfectly full binary tree.

30
00:02:09,510 --> 00:02:17,850
Now, if you have a perfectly full binary tree, and if this tree over here has n nodes, the number

31
00:02:17,850 --> 00:02:23,100
of leaf nodes this tree has will be approximately n divided by two.

32
00:02:23,100 --> 00:02:27,360
Now let's quickly take a side note to understand why this is the case.

33
00:02:27,360 --> 00:02:35,550
Okay, now in a perfectly full binary tree, if h is the height of the binary tree, then the number

34
00:02:35,550 --> 00:02:40,860
of nodes in that binary tree will be two to the power h plus one minus one.

35
00:02:40,860 --> 00:02:45,630
Now over here notice that h is equal to two okay and two to the power.

36
00:02:45,630 --> 00:02:51,330
Two plus one will be two to the power three minus one two to the power three minus one is eight minus

37
00:02:51,330 --> 00:02:52,380
one which is seven.

38
00:02:52,380 --> 00:02:59,130
And notice over here in this perfectly full binary tree where height is equal to two, there are indeed

39
00:02:59,130 --> 00:03:00,390
seven nodes.

40
00:03:00,390 --> 00:03:03,870
Now over here we have four leaf nodes.

41
00:03:03,870 --> 00:03:09,930
And to get the number of leaf nodes we'll just have to do two to the power h which is two to the power

42
00:03:09,930 --> 00:03:10,770
two over here.

43
00:03:10,770 --> 00:03:12,300
And that's equal to four.

44
00:03:12,300 --> 00:03:18,150
Now when we do four divided by seven that's approximately half of the nodes okay.

45
00:03:18,150 --> 00:03:19,200
Or over here.

46
00:03:19,200 --> 00:03:25,230
Also you can think of it in this manner two to the power H divided by two to the power H plus one minus

47
00:03:25,230 --> 00:03:27,750
one is approximately half okay.

48
00:03:27,750 --> 00:03:33,900
And if it was just two to the power h divided by two to the power h plus one, it would have been exactly

49
00:03:33,900 --> 00:03:34,260
half.

50
00:03:34,260 --> 00:03:38,670
Now we are saying approximately half because over here we have a minus one.

51
00:03:38,670 --> 00:03:39,360
All right.

52
00:03:39,360 --> 00:03:46,500
So we have discussed that in a perfectly full binary tree there are approximately n by two leaf nodes.

53
00:03:46,500 --> 00:03:53,250
Now let's use this to come up with the time complexity for the approach that we discussed in the approach

54
00:03:53,250 --> 00:04:02,040
video, we have seen that we have to visit every root to leaf path, because the nodes can have positive

55
00:04:02,040 --> 00:04:04,170
as well as negative values.

56
00:04:04,170 --> 00:04:06,900
So we have to visit every node.

57
00:04:06,900 --> 00:04:12,810
And because there are n nodes visiting every node will need work of the order of n.

58
00:04:12,810 --> 00:04:22,350
Now in these n by two cases where we are at leaf nodes, we potentially need to do O of H operations,

59
00:04:22,350 --> 00:04:29,730
because if the values of the nodes starting at the root node till that particular leaf node adds up

60
00:04:29,730 --> 00:04:36,120
to the target sum, then we would have to make a copy of that particular cur and append it to the results

61
00:04:36,120 --> 00:04:36,360
array.

62
00:04:36,360 --> 00:04:43,560
And making a copy of cur is an operation which takes up work of the order of the size of the current

63
00:04:43,560 --> 00:04:43,920
array.

64
00:04:43,920 --> 00:04:51,210
And because h is the height of the binary tree, the number of elements in cur will be of the order

65
00:04:51,210 --> 00:04:51,780
of H.

66
00:04:51,780 --> 00:04:59,760
So that's why in the n by two leaf node cases, we potentially may need to do o of h operations.

67
00:04:59,910 --> 00:05:04,530
So we need to do O of N operations to visit every node.

68
00:05:04,530 --> 00:05:08,310
And if I divide this n into n by two.

69
00:05:09,840 --> 00:05:11,730
And n by two.

70
00:05:13,170 --> 00:05:18,300
Where these n by two represents leaf nodes and these are the other nodes.

71
00:05:18,300 --> 00:05:24,300
We have seen that in the case of the leaf nodes we may have to do O of H operations.

72
00:05:24,300 --> 00:05:28,620
And in the other cases we are just doing constant time operations.

73
00:05:28,620 --> 00:05:37,050
So that's why the time complexity of this approach is of the order of n by two into one plus n by two

74
00:05:37,080 --> 00:05:38,040
into h.

75
00:05:38,040 --> 00:05:41,880
And this over here simplifies to n into h.

76
00:05:41,880 --> 00:05:48,240
So that's why the time complexity of the approach that we came up with is of the order of n into h.

77
00:05:48,330 --> 00:05:50,340
Now let's make some space over here.

78
00:05:50,340 --> 00:05:53,400
Now in the worst case scenario.

79
00:05:54,130 --> 00:05:58,450
And that would be the case where we are given a skewed binary tree.

80
00:05:58,450 --> 00:06:03,190
The height of the binary tree can be of the order of n, right.

81
00:06:03,190 --> 00:06:09,760
And that's why the worst case time complexity of this solution is of the order of n into n.

82
00:06:09,760 --> 00:06:10,180
Okay.

83
00:06:10,180 --> 00:06:13,720
And again, a skewed binary tree is something that looks like this.

84
00:06:13,720 --> 00:06:17,920
And notice over here the height is equal to n itself okay.

85
00:06:17,920 --> 00:06:24,370
So that's why the worst case time complexity of the solution that we came up with is of the order of

86
00:06:24,370 --> 00:06:25,150
n square.