Welcome back.
So far we have understood what the question asks us to achieve.
We have understood the Tower of Hanoi problem, and we have also understood that we can use recursion
to solve this question.
In this video, let's first develop an intuition regarding the approach that can be taken to solve this
question.
For this, let's take four cases.
The case where there is just one disk given to us.
If there are two disks given to us, three disks given to us, and then we'll generalize what we learn
from these three scenarios and apply it to the general case where n disks are given to us.
So let's start with the first case.
Let's say we are just given one disk.
So the problem would look like this.
We have to move this disk from round one to round three.
And this is pretty straightforward and easy.
We can just move it from rod one to rod three right.
So this is straightforward.
Now what about the scenario where we have two disks.
So it would look like this.
Again we have three rods.
And the two disks are over here.
Now the intuitive approach of solving this would be we would move this particular disk over here to
rod two.
And then we would move this disk the orange disk to rod three.
And then we can just move this disk over here on top of the orange one.
And we would have solved the question right.
So again this also is pretty straightforward because we are just dealing with two disks and it's pretty
intuitive.
Now an interesting observation over here.
Notice that we did not move this particular disk over here directly to rod number three.
Because if we did that then we would have this rod over here.
And then the orange one cannot be placed on top of it, because it would violate the condition that
a bigger disk cannot be on top of a smaller disk.
So the approach that we have taken is first, we move the smaller disk to the helper or auxiliary rod.
And then once we have the larger disk at the desired position, we move the smaller disk on top of it.
Now let's proceed to the case where we have three disks.
Now this case over here is interesting.
How would we solve this?
The approach that we could take is that we.
Would have to first solve the case where we just have two disks, which is something we already know
and remember.
We discussed that we cannot move the smaller disks directly to the desired destination, because if
we do that, then we would have to place this one, the orange one on top of it, right?
It would look like this.
And then the next move would be placing the orange disk on top of these.
But this is a violation of the condition.
So we cannot do this.
But rather than that what we can do is first move these two disks to road number two.
Once we have achieved that it would look like this.
And remember, this step over here is a recursive step, right?
Because we already know how to do this because we have discussed the case where we had two disks.
So over here we have three disks.
So we are aware of how to solve the scenario where we have two disks.
And we're just going to use that to move these two disks from road one to rod two.
So it would look like this.
Once we have achieved this, we would just move this disk over here from rod one to rod three and it
would look like this.
And then again we would have a recursive call to move these two disks from rod two to rod three.
So this is how we would solve the case where we have three disks.
Now let's use what we have learned over here and apply it to the general case where we have n disks.
So let's say we have n disks over here.
The sub problem would be having n minus one disks.
And we just have to move these n minus one disks recursively from rod one to round two.
And it would look like this.
So once we have achieved that we can move the largest disk over here from rod one to rod three.
So that would look like this.
Once we have achieved that.
So we have the biggest one over here.
And then all we need to do is again, recursively move these n minus one disks from rod to to rod three.
So they would be on top.
So these n minus one disks would be on top of the biggest disk.
And we would have solved the question without violating any condition.
So this is the approach that we will take to solve this question.
So let's quickly summarize what we have learned over here about the approach, the base case, or the
simplest or the last valid case.
If there is just one disc and we have seen that, that's pretty straightforward.
Just move the disk from rod one to rod three.
And then we have also discussed the recursive case over here which involves three steps.
So the first step is to move n minus one disks from rod one to rod two.
Notice this is not the final destination rod, but it's the helper or auxiliary rod.
So this is the first step in the recursive case.
And then we have to move the nth disc.
From round one to round three.
And then finally again, we have to move these n minus one disks from the auxiliary or helper rod to
the destination rod.
So this is how we can solve this question.
In the next video let's draw out the recursion tree.
And that will make it very easy to proceed and code out the solution, as well as analyze the time and
space complexity of the approach that we have come up with.