Hello all and welcome back.
So in this video let us now continue our discussion.
And now let's discuss a question which you all have to do.
And the question is as follows.
So given a height okay we have to tell number of possible binary trees.
So in this question we will be provided with a height.
Let's say initially the height is one.
Now we have to tell how many binary trees are possible with this given height.
For example, for height one, this is one binary tree which is possible for height two.
Binary tree which is possible is something like this.
So we can have a left child.
And we can have a.
Right child.
Along with that of course.
Both the child's.
Now pretty sure that you must have learned about binary trees in the module as well as what exactly
height is.
How do we define the height?
Now next can be height equals three.
For this particular height we can have many binary trees.
So let's say something like this.
This is having height two.
Now we can have this.
Similarly.
This is also a binary tree with height three right.
So there are actually many possible for height three.
We will not be able to draw all of them.
And the answer comes out to be 15.
Now at this point, since the question is clear, I want all of you to just pause the video once and
think that what exactly can be the approach?
Brute force, recursion, iteration, any approach which you are able to think to get to our answer
like how can we find the answer if we have a question given like this?
Great.
So I guess many of you must have thought about the answer.
Now, the very first intuition, which most students guess for this particular question is something
like this.
So let's say we have a tree here.
Let us consider the tree for.
Let me move it here.
Height three.
What we can do here is we have this tree with the height two.
Now we have at this particular level.
At this particular level we can have four nodes.
Right.
So one, two three and four.
Now then what we can do is we can take different combination of these nodes.
Right.
So different different combination when these nodes will be present or not.
In my binary tree.
That would give us two to the power four.
So two to the power four are all the combination.
If we are taking any one of them, all four of them, none of them.
These are all the combination which we have in front of us.
Now we have to subtract one here.
The reason is that in the case when none of these nodes will be present, the height will become two,
right?
Just like this tree where I don't have any nodes present.
Okay.
So the answer which I get in this particular case is.
One minute.
Yeah.
So answer is 50, which seems to be the right answer.
Now let us try this on let's say for a single node as well for a height two as well for a height two.
This is our one node.
Now I will be taking different combination of nodes at this level, which will give me two to the power,
two minus one.
And that will be four minus one equals three.
So seems like this is also giving us the right answer.
So we one minute.
Yeah.
So we saw that how here the answer was coming out to be three.
Here it is coming out to be 15.
and we are able to get the answer for this particular with this particular approach.
Now let us try to see if this particular approach it can fail somewhere as well.
Let us again draw the tree for height three first.
Okay.
So this is one tree which we have for height three.
Now for height four okay.
So let me write it here for height two.
For height four we will say that okay I have now these eight places.
Right.
Eight places.
So two to the power.
Eight minus one.
That should be our answer, right.
Because all I am doing is with the approach which I thought of.
I am just taking all the combinations when my node can be there to make the height tree or to make the
height four.
This comes out somewhere to be 256 minus one equals 255, which unfortunately is the wrong answer if
our height is four.
This is not the answer which we should get.
Answer is somewhere between three.
If I remember it right, it was somewhere around 343 or something, or 315, I guess.
Yeah, 315 was the answer.
Okay.
So we will check that as well when we write the code.
So let's see what we are missing out here everyone.
The problem is that yes we are able to make binary trees which are balanced and with a given height
we are missing out on some cases.
One of the case which we are missing out is something like this.
So I have a tree.
This makes the height three and this particular tree.
It is having the height four and it is balanced as well.
So the problem is we are assuming.
That Tree with h minus one height will be complete.
So that is the problem in this particular approach.
Here we are assuming that tree with this h minus one height will be complete.
That was something which we saw here as well right.
This is a complete binary tree.
And now we were trying to add the nodes here.
Although this will give us many answers, we will still lose out on cases like this where this one is
not complete and still the tree is completely balanced.
Right, everyone.
So again, remember in the question it is given and asked to create a tree which is balanced.
Okay.
Number of possible binary tree.
Let me write that as well.
Possible balanced binary tree okay.
So in the question as well you will see the same thing.
What was balance.
The height difference should not be greater than one.
Okay great.
Now let us try to think.
Now, I am pretty sure many of you might have the idea how to do it.
So let us go to the new page and see how exactly can we solve it in trees?
Question.
We always make sure that we are thinking like a tree in this manner, right?
So this is how we used to think about our tree.
Now in this particular tree, if you think, let's say I want the height to be H, okay, what are the
different different heights which my left and right subtree can have if I want it to be balanced as
well?
Okay.
And balanced.
Here I feel that the first height can be h minus one and h minus one.
So the left one can have h minus one height, and the right one can also have h minus one height.
Okay.
So again see whenever we are trying to solve these questions, always try to think that how you can
break your problem In such a way that it is a subproblem.
Okay, now by thinking around like a tree and a subtree structure, I am able to ask my recursion that
hey, can you give me for h minus one?
Then I will try to form for my h.
Okay, great.
Other can be.
If the height here is h minus one, then I think it can have a h minus two height as well as still balanced.
Because.
Difference is less than or equal to one.
Similarly this can have h minus two if this has a h minus one height.
So all I have to do here in this particular question I can just ask my recursion that hey get me the
h minus one okay.
And get me the h minus two.
Once I get these answer from my recursion, All I have to do for my answer.
Okay, let me write it down in green.
I can just directly say that my answer is going to be something like this.
So I am assuming this to be h1 h1 into h1.
Okay, the first one that is the first plus two into.
H1 into h2 right.
So this will give your full answer for this question because we have now worked around all the combinations
which are present.
I hope the same is possible if same is understandable.
Everyone.
Let me quickly help you revise what exactly happened, because this is a little different question than
the one you have solved for trees.
The question asked us to tell the count, okay, tell the count number of possible balanced binary tree
with given height.
We do it for h1, h2 and h3 okay.
We saw that okay.
How many trees are possible Based on this understanding, I discussed what is the major intuition which
most students have that let's say we have these nodes and I just need to have different combination
of these nodes, which is coming out to be two to the power four.
And of course, we have to subtract one for the case when none of these nodes will be present.
Similarly, this seems to work for h two when height is two, when we move to h equals four, this kind
of start giving us an error.
The problem is that we have missed out on some cases and the cases were something like this.
Okay.
So again we have to make sure that we are overall considering each and every case and making the balanced
binary tree great.
Now with this approach not working for us, we just went down to our basics and started thinking that
about our tree in this manner, the way we used to think when we solved our problem.
The constraints are that given the height h and that it is balanced.
Okay, we have to tell what will be the height that these subtrees can have.
Now, if I have to keep them balanced, either they can have the same height or they can have the height
difference maximum equal to one.
And if it is given that the whole tree has a height of h, then of course it can be just h minus one
or h minus two, so that the difference does not become greater than one.
Okay.
So pretty sure that.
Now this is a lot clear everyone.
Now what I want all of you to do in your coding exercise.
Please make sure that you try out this question.
You have to make sure to solve the question by first writing the recursion code.
Then let's memorize that solution.
And once the Memoized solution is clear, then I'm pretty sure the tabulation or pure DP approach you
will be able to write as well.
Okay, so great everyone please try out this in the coding exercise.
And then we are going to discuss it in the next video.