1
00:00:00,260 --> 00:00:02,330
Hey there and welcome back.

2
00:00:02,690 --> 00:00:12,350
In this side note, I want to discuss how we can find the upper bound of the number of nodes in a recursive

3
00:00:12,380 --> 00:00:16,700
tree where every node has a certain number of children.

4
00:00:16,700 --> 00:00:23,060
For example, over here this node has three children, and each of these nodes have three children.

5
00:00:23,060 --> 00:00:25,760
So over here you have one node.

6
00:00:26,240 --> 00:00:28,640
Over here you have three nodes.

7
00:00:28,640 --> 00:00:34,040
And over here in this level you have three into three which is nine nodes.

8
00:00:34,040 --> 00:00:36,920
So this is equal to three to the power one.

9
00:00:36,920 --> 00:00:39,920
And this is equal to three to the power two.

10
00:00:39,920 --> 00:00:44,570
And this over here is equal to three to the power zero.

11
00:00:44,570 --> 00:00:52,700
Now if we were to extrapolate this to n levels, what would be the number of nodes in this recursive

12
00:00:52,730 --> 00:00:53,180
tree.

13
00:00:53,180 --> 00:01:00,260
So the number of nodes would be three to the power zero plus three to the power one plus three square,

14
00:01:00,290 --> 00:01:04,010
etc. up to three to the power n minus one.

15
00:01:04,010 --> 00:01:09,590
Now why do I have three to the power n minus one as the last term over here?

16
00:01:09,800 --> 00:01:16,820
Notice that from the pattern that we see over here in level one, the number of nodes is three to the

17
00:01:16,820 --> 00:01:18,650
power one minus one.

18
00:01:18,650 --> 00:01:25,880
In level two, the number of nodes is three to the power two minus one, and in level three the number

19
00:01:25,880 --> 00:01:28,970
of nodes is three to the power three minus one.

20
00:01:28,970 --> 00:01:35,570
So that's why in the nth level you will have three to the power n minus one nodes.

21
00:01:35,570 --> 00:01:43,100
So if you just add up all of these values, then we can get the total number of nodes that are there

22
00:01:43,100 --> 00:01:44,780
in this recursive tree.

23
00:01:44,780 --> 00:01:48,920
Now for this let's make use of geometric progression.

24
00:01:48,920 --> 00:01:55,310
Because this over here is just a geometric progression where you get every next term by multiplying

25
00:01:55,310 --> 00:01:57,260
the previous term by three.

26
00:01:57,290 --> 00:02:07,610
Now sum up to n terms in a geometric progression, which is s n sum up to n terms is equal to a, which

27
00:02:07,610 --> 00:02:13,040
is the first term into r to the power n minus one by r minus one.

28
00:02:13,040 --> 00:02:18,530
So s n represents sum up to n terms and a is the first term.

29
00:02:19,150 --> 00:02:22,300
And R is the value that you keep multiplying with.

30
00:02:22,300 --> 00:02:27,400
So for example, in this case r is equal to three and n is the number of terms.

31
00:02:27,400 --> 00:02:31,600
So in this case we are going from zero up to n minus one.

32
00:02:31,600 --> 00:02:34,720
So this would be a total of n terms.

33
00:02:35,320 --> 00:02:42,730
And over here the sum up to n terms, or the sum from three to the power zero up to three to the power

34
00:02:42,730 --> 00:02:49,750
n minus one will be equal to one into three to the power n minus one by three minus one.

35
00:02:49,780 --> 00:02:51,550
Now why do I have one over here?

36
00:02:51,550 --> 00:02:56,230
Because the first term is equal to 1 or 3 to the power zero.

37
00:02:56,230 --> 00:02:59,590
And then for r I have substituted three over here.

38
00:02:59,590 --> 00:03:05,170
And then for n I have kept n itself because we have n terms in this sequence.

39
00:03:05,170 --> 00:03:13,870
So sum up to n terms or this sum over here is equal to one into three to the power n minus one by three

40
00:03:13,870 --> 00:03:14,650
minus one.

41
00:03:14,650 --> 00:03:19,780
And this simplifies to three to the power n minus one divided by two.

42
00:03:19,810 --> 00:03:24,370
Now over here n is the number of levels.

43
00:03:24,400 --> 00:03:32,170
Now how can we write this in terms of the height or the maximum height or maximum depth of the tree

44
00:03:32,170 --> 00:03:33,130
which is given to us?

45
00:03:33,130 --> 00:03:38,620
Now again, notice from the pattern n is equal to the height plus one.

46
00:03:38,620 --> 00:03:42,490
And with height I mean maximum height of the recursive tree.

47
00:03:42,490 --> 00:03:49,630
So in this case height or the maximum height is the maximum number of edges when you go from the root

48
00:03:49,630 --> 00:03:51,010
to the leaf.

49
00:03:51,010 --> 00:03:53,170
And in this case that's equal to two.

50
00:03:53,170 --> 00:03:57,370
And for example over here the level is three but the maximum height is two.

51
00:03:57,400 --> 00:03:59,980
So n is equal to height plus one.

52
00:03:59,980 --> 00:04:03,880
So let me substitute height plus one instead of n over here.

53
00:04:03,880 --> 00:04:11,410
So the sum or the number of nodes of this recursive tree would be three to the power height plus one

54
00:04:11,410 --> 00:04:13,360
minus one divided by two.

55
00:04:13,390 --> 00:04:21,460
So we can say that the maximum number of nodes in this recursive tree, or the upper bound of the number

56
00:04:21,460 --> 00:04:28,420
of nodes in this recursive tree, can be three to the power the height of the recursive tree plus one.

57
00:04:28,420 --> 00:04:30,400
Okay, so that's this part over here.

58
00:04:30,970 --> 00:04:34,840
And I'm just avoiding these constants because I just need an upper bound.

59
00:04:34,840 --> 00:04:39,910
This value over here will definitely be greater than this value over here, because you're subtracting

60
00:04:39,910 --> 00:04:42,490
from this and dividing from this over here.

61
00:04:42,490 --> 00:04:50,170
So the upper bound of the maximum number of nodes in this type of a tree is equal to three to the power

62
00:04:50,170 --> 00:04:54,130
height of the tree, maximum height of the tree plus one.

63
00:04:54,130 --> 00:05:03,310
Now instead of three, if this was a tree where every node had n children, then the maximum number

64
00:05:03,310 --> 00:05:08,890
of nodes in this type of a tree would be n to the power height plus one.

65
00:05:08,890 --> 00:05:11,230
Okay, so n to the power height plus one.

66
00:05:11,230 --> 00:05:13,300
Now this was a quick side note.

67
00:05:13,300 --> 00:05:19,810
Now let's see how we can use this in the next video for determining the space and time complexity of

68
00:05:19,810 --> 00:05:22,390
the approach for solving combination sum one.