Hello all and welcome back.
So in this video let us now move forward.
And now let's try to write down the solution of the problem which we discussed in the last video.
That is to find the balanced binary tree for a given height h.
Now I'm pretty sure that you must have tried this solution yourself, and will be able to at least write
the recursive code.
We discussed the same thoroughly with in-depth explanation and example in the last video, so if you
have not given this a try, I will highly suggest to please make sure that you are able to first spend
some time on this before you see the solution.
Now talking about the solution, the approach is going to be the same.
We are going to think of our tree in this manner.
Where each node will have two subtrees.
Now we discussed that how we can have three cases because it is a binary tree and it's balanced as well.
We have to make sure that the height follows some order.
Right now, if it is asked that all these binary trees are having a height, which is H, then of course
the binary tree or the tree which is this subtree, they can take some particular values.
Now we discussed how that value can be h minus one and h minus one.
Then it can have h minus one and h minus two and h minus two and h minus one.
Now do you think that the height can be h minus two and h minus two?
Well, pretty sure that you must be able to guess that it is not possible.
The reason is that if the height of both the subtrees are h minus two, Then we will get the overall
height as h minus one, which is wrong because we want the height of our tree to be h.
Okay, great.
With that in line, now let us try to write the skeleton or the code for this particular case with respect
to recursion.
Now we can say def count balanced.
Binary tree recursive.
And we will be given a height h.
Okay great.
First and foremost, just as we do in recursion the base case.
If our height equals zero or height equals one, then I think we should just return one because we discussed
in the last video, if the height is one, then only a single node is possible.
If height is zero then we can say that a node is null, right?
So only a single tree is possible, which is a null tree.
Okay, so this is our base case everyone.
Let me write down for zero as well.
For zero we will say that a single tree of height of value, null or none, is possible.
Okay, great.
Now we discussed how we have to get this H minus one and h minus two trees.
Okay.
So pretty sure that you must be able to understand why a recursion that if I am able to get these trees,
I just have to pass this subproblem or smaller problem to my recursion.
Okay.
For example, I can say h one equals count balance binary trees recursive h minus one and h two.
I can say count balanced binary tree recursive h minus two.
So the same problem I am just sending to my recursion and asking it to solve.
Okay.
So this is the recursive call.
Let me write down these three steps, though we have seen them multiple times whenever we do any recursion
question, the first is the base case.
Then we have the recursive call.
And then we have our work okay.
Great.
So this is done.
This is also done.
Now let us see for our work.
Should we add these h1 h2 or should we multiply them okay.
So these h1 and h2 they are giving me the subtrees which are possible.
And I have to get all the combinations of these subtrees with respect to this root okay.
So let's say I am getting three subtrees here and three subtrees here.
Now all the combination will be three into three nine okay.
Not three plus three six.
How you can understand it in an easy manner.
So let's say when we have two dices okay.
If we have two dices then the total number of your outcomes of the dices are six into six.
Because each dice has six possible options, all the combinations between these two dices is equal to
six into six, which is 36 and not six plus six.
Okay, so pretty sure that this must be clear now everyone.
So with that clear now, let us try to write down the answer.
If we have to write the code, the answer will be something like this.
Answer will become h1 into h1.
Plus, if you pay attention here, this is just the same thing.
We are saying that once the left subtree can have h minus one height and the right can have h minus
two and the other way round.
Okay, so directly I can write it like this.
Now pretty sure till now we have done so many questions, lots of coding.
We have done so these things will be clear, right?
I am just trying to write down this directly.
Okay.
So let us write down the answer.
Everyone now answer equals h1 into h1 plus two into h1 into h2.
And we can return this answer.
Let us try to see if we are able to get the right answer.
So for one one minute okay.
We are not printing it.
So let us print that as well.
Great.
So it's one then for two it's three for three.
It's 15 for four its 315.
Okay, so in the coding exercise, of course you must have solved and many examples will be given to
you.
So pretty sure you must have checked it via that thing.
Now one thing more just to just so that you are aware when you will see this solution in any other language.
Here the solution is increasing very quickly, right?
For example, for three we had just 15 as the possible binary trees.
But for four you will see that the number has gone to 315.
If I make it five it will surely be in thousands or something, right?
See, the reason I think all of you can see we are doing so much squaring and power.
Okay, so that's the reason the number will increase a lot quickly.
Now Python doesn't have any foundation so you will be able to see the answers pretty nicely.
That is not a problem in Python, but you must be aware that in other languages, or if you will see
this solution somewhere else, then to limit our answer, okay, to limit our answer into the overall
range of an integer, we normally use a mod.
Let me write this down because it's very important in some other languages.
To prevent overflow.
The answer is bounded
by taking mod of a mod.
With respect to a number.
Now this is not required in Python as well as in your initial dictionary.
It is not required.
This overall concept is something which we use a lot in competitive coding, where we have to make sure
that the answer doesn't go out of bounds.
In Python, as we have, as we are already aware, it is dynamic in nature, so the size is increases
as the value increases.
But in many places you will see that a ten to the power 8 or 6 plus seven will be used to bound our
answer so that it doesn't go out of the overall your flow.
Okay.
Great.
So now let us move forward everyone and see are we actually solving some problems or some problems again
and again.
Right.
So for that again it's pretty straightforward to understand.
I can draw the tree here as well.
And we will then see the same in tool as well.
So for for.
I will be making one call to.
Three.
And then one call to two.
Okay.
Three will make a call to.
Two.
And it will make a call to one.
Two will similarly make a call to one and two zero.
So again because the number is small initially we can see some overlapping subproblems as it will increase
just like Fibonacci.
We will have a lots of call rather this.
Overall I would say relation recurrence relation is very much like the Fibonacci number, where we are
dependent on n minus one and n minus two, right.
So the complexity also.
Then I can write complexity.
Of this code is two to the power n right everyone.
Because just like Fibonacci number we are making calls on a number less than me and two less than me.
Okay, so let us see that in two less.
Well, this is the code.
So this is the code which we have written.
Okay.
Let's say if I draw it for five.
So see everyone how many calls are getting made.
This is the answer.
So just this calculation is different.
Everything is same.
So many of you might see that this is exactly like Fibonacci number code or Fibonacci number.
So this 3322.
Right.
All these sub problems they can be they are overlapping subproblems which can be avoided.
You can see that function returns 1.09 e plus five.
That is one into ten to the power five.
You can just assume so towards the 100 K mark.
Right.
Great.
So pretty sure that by seeing this tree you are able to understand that how exactly we have many subproblems
which we need to solve.
Okay, great.
Then I think many of us know what we can do for cases like this.
Let us go back in our code and try to now apply the memoization.
That is a case where we will try that we are not making these calls again and again and solving our
answer.
Great.
So before that, just let us also have this tree so that we can have this in our notes.
Just give me a second.
Yeah.
So let us have this tree and we will then see how it changes once we have applied memoization.
Okay.
Great.
So let us go back to our VS code everyone.
And now let's try to add memoization into our code.
Now let us just copy this code because major things will be the same.
We can have a memoization, uh, array or list here.
So memoization of H one.
One minute.
Yeah.
Memoization of h minus one equals h one.
Or we can just directly save it here.
Right.
So we can have it like this.
Yeah.
So before just making sure that I send to answer or sorry I do the calculation and return my answer.
I am just trying to save these answers.
Okay.
So this is how we used to do our memoization, right everyone.
So just saving these answers for h minus one.
This is the answer.
And here what we have to do if memo of h not equals minus one then we can return this.
Now I'm pretty sure that by doing problems you will have a good idea that.
How are we applying this?
Okay so great everyone.
Now we can just have memo equals minus one into h plus one.
Okay so I am using h equals six here.
Let's say I'm sending or let's make it five so that we are able to see in diagram as well.
And yes I think this works fine.
So let us send H here only.
And let us call this memoization okay.
So pretty sure that you must have understood.
But I will still repeat what I have done.
Just first I have checked if I already have the answer.
If I have the answer, then again I will not be calculating it right?
Similarly, once I get the answers, I am just saving them.
I could have directly saved them in H without using H1, but again, I think you should be exposed to
multiple ways you can do the problem initially.
It's not a problem if you are making lots of variable, all is fine.
Your variable you know, are taking very less space so everything is fine.
The understanding is paramount.
You should be able to understand each and everything.
Okay so h minus two.
H minus one.
We have saved here everyone.
Then we calculate our answer.
And finally we are saving our answer.
Okay, great.
So with this in mind I think we are good to run this code.
Let me just quickly run this and seems like we are getting our answer.
Okay, great.
So for this particular code, let us now go back to Python Tutor and try to see how exactly this will
run.
Okay, so very similar to Fibonacci again.
But I still want that you understand how exactly memoization will happen.
That's the first thing.
Second thing, I want to make sure that you understand how to change code like these two tabulation
approach.
Okay.
So let it run everyone.
Great.
It is saying that we have made an error here.
Okay, we have called recursive here.
My bad.
Let us first try to call memoization to see if our code works.
Okay.
Same mistake.
What is the error?
Yeah.
So we are not sending this memo array which is our mistake.
Okay.
And memo here as well.
Yeah.
So we seem to get the answer.
Same changes.
Let's make it into this as well.
Let us send memo.
Memo table.
And we can just call this everywhere.
Great.
So okay again it's giving.
Yeah.
We have forget to pass memoization list here.
A minute.
Why is it not letting me edit?
Okay.
Great.
So, yeah, we have everything in place.
Everyone.
I want all of you to focus that how our memoization list is getting filled.
Okay.
Because that is going to give you the idea.
How exactly are we doing this question?
Everything is minus one initially.
Let us move forward.
Now first I'm calling for H5.
We have five here okay.
It's going to call for four and three.
See four gets called then three gets called.
So we started from top okay.
And then going towards down okay.
Top down approach.
That's why it is known as top down approach.
Now what we have to do three will call 222 will call two one and one is our base case Yes.
Okay.
For base case, we could have saved and made the change here, but again, we are just making sure that
we are.
We know that the answer is trivial for that.
So we can get that.
Great.
Once we have this answer for one and zero, then we can move forward.
Okay.
In a way, if you understand, though, we are not referring to this memo for zero and one.
In a way we have this answer already.
So we are not spending more time.
That's the basic idea, right?
We have to save this answer for one and zero.
We know the answer, so maybe we don't need to save it as well.
Just that I should not be spending a lot of time in solving this particular approach, or solving for
a particular number for which we have already solved.
Great.
So let us move forward.
Now we will get the answer for two.
We have the H1 here and H2 here for two.
Okay.
So for this let me show you an image as well.
for these two I have the h1 and h2.
Based on that, I will frame my answer, which is going to be three because this is the formula getting
applied.
Now if you would have done h1 plus h2.
This would have exactly been the Fibonacci code.
So I hope you are also able to understand that how your understanding of a particular approach, a particular
function, a code or a question will help you to solve more questions as well going forward.
Okay.
And that is the main overall I would say understanding or main crux of DP.
If you understand, if you do and properly able to get the intuition of few of the questions right,
then the variations will be very much easy for you.
Now in this course again we have introduced all those variations so that once you do them, each and
every other question you will be able to do based on that intuition.
Okay?
Please make sure that you are spending that time to do the question if you will just see the solution
for each and every question, you will never be able to solve the deep question.
Okay, the basic idea always is to understand that how the questions are related to each other.
The language will be different.
The overall way to form the intuition will be different, but code is going to be a lot straightforward
and similar.
Okay, so now let us move forward everyone.
We see that two will now get filled.
So zero and one we have filled as well because we would have made call for that.
We have saved them here when we saved it right H minus one and h minus two.
Now answer will get calculated so we can see the answer here.
Answer is three.
Before returning I am just saving my answer.
So I have the answer here which is three.
Great.
So balance is memoization.
We have the answer here for h1 h2 call will be for n h is equals to one.
Okay.
Again we have the answer there so we can get the answer directly.
Now we can just move forward, everyone and get the answer for three and save it in our this memo list.
Okay, great.
Let us now move forward similarly for four.
It will now make one call to three which it has got the answer.
Second call on two.
It will directly get the answer.
Pay attention.
Second call on two.
Okay.
When it makes the call, it directly has the return value.
No more need to go deep down the recursion tree and we can get out.
One more thing.
More.
I hope you are able to see how we are filling in these things, right?
Exactly the same.
Just like in Memoize or in Fibonacci.
Just the overall I would say calculation is different.
Okay.
Now four will get filled with the answer.
Now again five will get filled.
Okay.
Five have both the answers.
Now five will call on four and three.
So see how quickly we are able to get the answer.
And then finally five answer is here, which we will store as well so that tomorrow, if it is needed
by 6 or 7, we can get that.
See, the whole is in a way filled from the bottom only, but we started from top.
If you are able to understand this memoization code, then you will never face problem in writing down
the tabulation or pure DP approach.
Because here we have seen in front of our eyes that how these this list has filled, that could have
given us enough idea that how we will write the pure DP solution.
Okay, great everyone.
So pretty sure this will be clear.
Now let us see this in image as well.
Again all these approaches to make sure that you have no doubts whatsoever.
Just when I click in this memoization we won't have these calls.
These three call.
We will not have these three and two okay.
This two call will not be calling anything beyond that.
so.
See?
And we know that.
Okay.
How fast the same can be.
Getting it from two to the power n to n is a very great optimization.
See how quickly in less steps we are able to get our answer?
Okay great everyone.
So pretty sure this will also be clear.
Now for the overall uh, that code finally okay.
For the bottom up pure deep code, I think we can just directly copy and use this.
So this is the same code which we wrote for your Fibonacci number, right, everyone.
So let us just write tabulation here.
And I'm pretty sure like maybe at this point you can pause the video and all of you will be able to
write the answer.
I'm pretty sure of that.
Okay.
So just that we are using N here.
So let it be n only n less than equal one.
We are returning one okay.
We are taking deep Here.
We take it as zero because we know we have to add it going forward.
Okay, great.
What is the change?
We have to do something like this.
Now you can take H1 and H2 as well.
Just that I'm pretty sure.
Now all of you will be a lot comfortable in writing this.
Okay.
And yeah this is the solution if you have seen this video properly, if you have done the Fibonacci
number as well, I'm pretty sure you must be very clear that how we have just derived the solution by
changing this formula or this calculation, because this is the only difference between the Fibonacci
number and this number.
Why am I making sure that you understand this?
Because I always want that you are able to spot these patterns when you solve these questions going
forward in dynamic programming.
Okay, great.
And I think yes, we have our answer.
So we can just call this with five and we are able to get an answer.
See?
Let us call it for maybe four and we get an answer as 315.
Because in Fibonacci, where we were adding the last two numbers, here we are just doing a different
calculation.
Nothing else is a problem.
Once you have understand the problem, once you have understand the solution, then it all boils down
to this particular code you are writing again and you will never face an issue.
And these are the things which are.
Interviewer is also very much interested to understand, because he will be able to see that yes, this
person is able to catch all these patterns, be it any tier one company like Google, Microsoft, Amazon,
Goldman, your startups as well.
You will be asked question based on this overall approach only.
Okay, so great everyone.
Pretty sure that you must have also written the solution.
And with this discussion, the whole idea will be a lot clearer.
Just to keep it in our notes.
Let me just copy this as well because I want that you have these notes to refer whenever you have an
interview.
So this is how your tree is going to change.
Okay.
So let me write down that as well.
From recursion.
To memoization.
Tabulation approach will of course be clear.
So this is just what we have done.
And we can see the calls getting reduced as well thanks to that tool.
Uh, pretty sure that this visualization approach, which I am using in each and every concept data
structure, which I have taught you till now, will be a lot helpful.
Okay, great.
So now get back to solving more questions, and let's meet in the next video to see how we can solve
more difficult questions, more approaches in the dynamic programming world.