Hey there and welcome back.
In this side note, I want to discuss how we can find the upper bound of the number of nodes in a recursive
tree where every node has a certain number of children.
For example, over here this node has three children, and each of these nodes have three children.
So over here you have one node.
Over here you have three nodes.
And over here in this level you have three into three which is nine nodes.
So this is equal to three to the power one.
And this is equal to three to the power two.
And this over here is equal to three to the power zero.
Now if we were to extrapolate this to n levels, what would be the number of nodes in this recursive
tree.
So the number of nodes would be three to the power zero plus three to the power one plus three square,
etc. up to three to the power n minus one.
Now why do I have three to the power n minus one as the last term over here?
Notice that from the pattern that we see over here in level one, the number of nodes is three to the
power one minus one.
In level two, the number of nodes is three to the power two minus one, and in level three the number
of nodes is three to the power three minus one.
So that's why in the nth level you will have three to the power n minus one nodes.
So if you just add up all of these values, then we can get the total number of nodes that are there
in this recursive tree.
Now for this let's make use of geometric progression.
Because this over here is just a geometric progression where you get every next term by multiplying
the previous term by three.
Now sum up to n terms in a geometric progression, which is s n sum up to n terms is equal to a, which
is the first term into r to the power n minus one by r minus one.
So s n represents sum up to n terms and a is the first term.
And R is the value that you keep multiplying with.
So for example, in this case r is equal to three and n is the number of terms.
So in this case we are going from zero up to n minus one.
So this would be a total of n terms.
And over here the sum up to n terms, or the sum from three to the power zero up to three to the power
n minus one will be equal to one into three to the power n minus one by three minus one.
Now why do I have one over here?
Because the first term is equal to 1 or 3 to the power zero.
And then for r I have substituted three over here.
And then for n I have kept n itself because we have n terms in this sequence.
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
minus one.
And this simplifies to three to the power n minus one divided by two.
Now over here n is the number of levels.
Now how can we write this in terms of the height or the maximum height or maximum depth of the tree
which is given to us?
Now again, notice from the pattern n is equal to the height plus one.
And with height I mean maximum height of the recursive tree.
So in this case height or the maximum height is the maximum number of edges when you go from the root
to the leaf.
And in this case that's equal to two.
And for example over here the level is three but the maximum height is two.
So n is equal to height plus one.
So let me substitute height plus one instead of n over here.
So the sum or the number of nodes of this recursive tree would be three to the power height plus one
minus one divided by two.
So we can say that the maximum number of nodes in this recursive tree, or the upper bound of the number
of nodes in this recursive tree, can be three to the power the height of the recursive tree plus one.
Okay, so that's this part over here.
And I'm just avoiding these constants because I just need an upper bound.
This value over here will definitely be greater than this value over here, because you're subtracting
from this and dividing from this over here.
So the upper bound of the maximum number of nodes in this type of a tree is equal to three to the power
height of the tree, maximum height of the tree plus one.
Now instead of three, if this was a tree where every node had n children, then the maximum number
of nodes in this type of a tree would be n to the power height plus one.
Okay, so n to the power height plus one.
Now this was a quick side note.
Now let's see how we can use this in the next video for determining the space and time complexity of
the approach for solving combination sum one.