Welcome back.
Let's now proceed and draw the recursion tree of the approach that we have discussed for solving the
Tower of Hanoi problem.
Now for drawing this tree, let's take the case where we are given three disks.
All right.
So the first call to the function that we're going to write will pass in the number of disks as three.
And we would want to move the disks from rod one to rod three.
And so let's say this is the from rod.
This is the two rod.
And this is the helper or auxiliary rod.
Now we have seen that because over here we have more than one disks.
What we will do is we will first move n minus one disks.
Or in this case that would be two disks from rod one to rod two.
So this is the first thing that we are doing right.
So this is going to be a recursive call.
So we are going to move two disks from rod one to row two.
And rod three in this case is going to be the helper or auxiliary rod.
Now again let me just draw out the recursion tree.
And then we'll also discuss how the algorithm is going to do it.
So again the algorithm first will complete this call before going to the next branch over here.
But for our understanding I'm just drawing the next step over here because we know we are going this
is going to achieve this result.
Once this is done, we are going to move the nth disk or that's the third disk.
In this case we're going to move the nth disk from rod one to rod three okay.
So that's going to be the next step.
And then once we're done with this we are going to do this step over here which is move the two disks
from rod two to rod three.
And in this case rod one is going to be the helper or auxiliary rod.
So this is how the algorithm would solve this problem.
Now remember this step over here is just a print statement.
And these two steps over here are recursive calls to the same function that we're going to write.
Because again notice we have more than one roots.
Now let's proceed.
How would this function over here.
Go ahead.
Let's take a look at that again.
We have more than one disk.
We have two disks over here.
So this over here is again going to recursively call the same function.
But before we take a look at that, remember when we are moving two disks from row one to row two.
Notice that the order is preserved.
Over here you have the green one.
And below that you have the blue disk.
And this order is going to be preserved over here.
So take a note of that.
Now let's proceed.
Let's make some space over here.
So we have to move two discs from rod one to rod two.
And because this is more than one disc, it's gonna it's going to move n minus one discs, which is
going to be two minus one.
That is one disc from rod one to the auxiliary or helper rod which is rod three in this case.
So we are going to move one disc from rod one to rod three.
And once this is done we are going to move the nth disc or the second disc in this case from rod one
to rod two.
And after this we are going to again move n minus one disks, which is again one disk in this case from
rod three.
Two rod two because that's what we want to achieve.
That's the final destination required.
So these guys over here are now at row two and we need to move them to rod two.
They are at rod three.
Now.
We need to move them to rod two.
So again we are having a recursive call to move disk one from rod three one disk from rod three to rod
two and rod one is the helper or auxiliary rod in this case.
Now this call over here, this recursive call over here will find that we just have one disk.
So we're going to move disk one.
From rod one two, rod three.
And over here in this recursive call we are going to move this one disk from rod three to rod two.
All right.
And again, remember these three statements over here are print statements because we're just moving
one disc.
Whenever we are moving one disc we are having a print statement.
Again.
Remember that's one of the conditions in the question.
We can only move one disc at a time.
So whenever we are having a recursive call inside the recursive call, whenever we reach the case where
we are dealing with one disc, we are having a print statement.
Now let's complete this branch of the recursion tree as well.
Let's make some space.
So over here we want to move two disks, these two disks from row two to row three.
Now because n at this place is more than one we are going to move n minus one disks which is one disk
from rod two to rod one.
And after that we are going to move the nth disk or disk two from rod two to rod three.
And after that we are moving these n minus one disks or one rod from rod one, because they are at rod
one at this point.
And the final destination for it is rod three.
So we are going to move them from rod one to rod three, and rod two is going to be the auxiliary or
helper rod.
So this is how we will solve this question again inside this recursive call.
Because n at this point is one we are going to have a print statement to move disk one from rod two
to rod one.
And over here also, because we have just one disk, we are going to have a print statement to move
disk one from rod one to rod three.
So these are all the print statements that we will have.
Notice that we will have seven print statements.
Now let's also quickly think whether this will actually work.
So let's think about this.
So first over here we are going to move rod one to rod three.
So let's just write that over here okay.
So we have rod one over here.
We have rod two over here.
And we have brought three over here.
Let's just see whether this call will actually achieve this desired state.
So initially we're going to move disk one from road one to road three.
So we're going to have disk one over here.
And disk one is the green one.
So let me probably write it as green.
For us to relate to this diagram over here.
So we're going to have the green disk over here.
And after that we're going to execute this print statement over here which is move disk two which is
the blue disk from rod one to row two.
So the blue one is going to be over here.
And over here.
We are going to have move disk one from rod three to row two.
So the green over here is going to be moved from rod three to rod two.
So the green disk is going to be over here.
And notice that we have achieved this arrangement where green is on top and you have blue below it.
And that's what you can see over here.
So notice this part over here has achieved this.
And after that over here we are moving disk three which is orange from rod one to rod three.
So that should be pretty straightforward.
So we have orange over here and over here again in this call.
Let's see whether these two disks are moved from rod to to rod three achieving this desired state.
So initially we're going to move disk one from row two to rod one and disk one.
Is the green one.
So the green one is going to be moved over here.
And over here we have disc two, which is the blue one.
The blue one is going to be moved from rod two to rod three.
So the blue one comes over here.
And over here we have disc one which is the green one from round one to round three, round one to rod
three.
So the green one comes over here.
And notice that we have achieved green blue orange green blue orange which was the desired order.
And these are now at rod three.
So yes our function is working.
And this is the recursion tree of the approach to solve the Tower of Hanoi problem.