1 00:00:00,500 --> 00:00:01,580 Welcome back. 2 00:00:01,580 --> 00:00:07,910 Let's now proceed and draw the recursion tree of the approach that we have discussed for solving the 3 00:00:07,910 --> 00:00:09,380 Tower of Hanoi problem. 4 00:00:09,380 --> 00:00:15,140 Now for drawing this tree, let's take the case where we are given three disks. 5 00:00:16,600 --> 00:00:17,260 All right. 6 00:00:17,260 --> 00:00:24,610 So the first call to the function that we're going to write will pass in the number of disks as three. 7 00:00:24,610 --> 00:00:30,010 And we would want to move the disks from rod one to rod three. 8 00:00:30,010 --> 00:00:32,410 And so let's say this is the from rod. 9 00:00:32,440 --> 00:00:34,300 This is the two rod. 10 00:00:34,600 --> 00:00:38,080 And this is the helper or auxiliary rod. 11 00:00:38,230 --> 00:00:42,730 Now we have seen that because over here we have more than one disks. 12 00:00:42,730 --> 00:00:46,930 What we will do is we will first move n minus one disks. 13 00:00:46,930 --> 00:00:52,990 Or in this case that would be two disks from rod one to rod two. 14 00:00:53,020 --> 00:00:54,880 So this is the first thing that we are doing right. 15 00:00:54,880 --> 00:00:57,070 So this is going to be a recursive call. 16 00:00:57,070 --> 00:01:01,390 So we are going to move two disks from rod one to row two. 17 00:01:01,390 --> 00:01:06,010 And rod three in this case is going to be the helper or auxiliary rod. 18 00:01:06,010 --> 00:01:09,910 Now again let me just draw out the recursion tree. 19 00:01:09,910 --> 00:01:13,660 And then we'll also discuss how the algorithm is going to do it. 20 00:01:13,660 --> 00:01:19,600 So again the algorithm first will complete this call before going to the next branch over here. 21 00:01:19,600 --> 00:01:24,940 But for our understanding I'm just drawing the next step over here because we know we are going this 22 00:01:24,940 --> 00:01:26,440 is going to achieve this result. 23 00:01:26,440 --> 00:01:32,260 Once this is done, we are going to move the nth disk or that's the third disk. 24 00:01:32,260 --> 00:01:38,800 In this case we're going to move the nth disk from rod one to rod three okay. 25 00:01:38,800 --> 00:01:40,210 So that's going to be the next step. 26 00:01:40,210 --> 00:01:47,260 And then once we're done with this we are going to do this step over here which is move the two disks 27 00:01:47,260 --> 00:01:50,650 from rod two to rod three. 28 00:01:50,650 --> 00:01:55,600 And in this case rod one is going to be the helper or auxiliary rod. 29 00:01:55,960 --> 00:01:58,810 So this is how the algorithm would solve this problem. 30 00:01:58,810 --> 00:02:02,920 Now remember this step over here is just a print statement. 31 00:02:04,190 --> 00:02:11,300 And these two steps over here are recursive calls to the same function that we're going to write. 32 00:02:11,300 --> 00:02:14,720 Because again notice we have more than one roots. 33 00:02:14,750 --> 00:02:15,980 Now let's proceed. 34 00:02:15,980 --> 00:02:17,990 How would this function over here. 35 00:02:18,020 --> 00:02:18,650 Go ahead. 36 00:02:18,650 --> 00:02:20,210 Let's take a look at that again. 37 00:02:20,210 --> 00:02:22,400 We have more than one disk. 38 00:02:22,400 --> 00:02:23,990 We have two disks over here. 39 00:02:24,620 --> 00:02:29,270 So this over here is again going to recursively call the same function. 40 00:02:29,270 --> 00:02:35,960 But before we take a look at that, remember when we are moving two disks from row one to row two. 41 00:02:35,960 --> 00:02:38,450 Notice that the order is preserved. 42 00:02:38,450 --> 00:02:39,890 Over here you have the green one. 43 00:02:39,890 --> 00:02:41,810 And below that you have the blue disk. 44 00:02:41,810 --> 00:02:45,290 And this order is going to be preserved over here. 45 00:02:45,290 --> 00:02:46,670 So take a note of that. 46 00:02:47,430 --> 00:02:48,780 Now let's proceed. 47 00:02:48,780 --> 00:02:50,400 Let's make some space over here. 48 00:02:51,520 --> 00:02:56,170 So we have to move two discs from rod one to rod two. 49 00:02:56,200 --> 00:03:03,220 And because this is more than one disc, it's gonna it's going to move n minus one discs, which is 50 00:03:03,220 --> 00:03:04,870 going to be two minus one. 51 00:03:04,870 --> 00:03:13,720 That is one disc from rod one to the auxiliary or helper rod which is rod three in this case. 52 00:03:13,720 --> 00:03:17,170 So we are going to move one disc from rod one to rod three. 53 00:03:17,440 --> 00:03:25,930 And once this is done we are going to move the nth disc or the second disc in this case from rod one 54 00:03:25,930 --> 00:03:26,950 to rod two. 55 00:03:29,120 --> 00:03:37,340 And after this we are going to again move n minus one disks, which is again one disk in this case from 56 00:03:37,340 --> 00:03:38,300 rod three. 57 00:03:39,320 --> 00:03:43,460 Two rod two because that's what we want to achieve. 58 00:03:43,460 --> 00:03:45,260 That's the final destination required. 59 00:03:45,260 --> 00:03:51,560 So these guys over here are now at row two and we need to move them to rod two. 60 00:03:51,590 --> 00:03:52,580 They are at rod three. 61 00:03:52,580 --> 00:03:52,970 Now. 62 00:03:52,970 --> 00:03:55,100 We need to move them to rod two. 63 00:03:55,100 --> 00:04:02,090 So again we are having a recursive call to move disk one from rod three one disk from rod three to rod 64 00:04:02,120 --> 00:04:08,060 two and rod one is the helper or auxiliary rod in this case. 65 00:04:08,330 --> 00:04:14,930 Now this call over here, this recursive call over here will find that we just have one disk. 66 00:04:14,930 --> 00:04:17,480 So we're going to move disk one. 67 00:04:18,530 --> 00:04:22,490 From rod one two, rod three. 68 00:04:22,490 --> 00:04:30,830 And over here in this recursive call we are going to move this one disk from rod three to rod two. 69 00:04:33,020 --> 00:04:33,680 All right. 70 00:04:33,680 --> 00:04:39,740 And again, remember these three statements over here are print statements because we're just moving 71 00:04:39,740 --> 00:04:40,670 one disc. 72 00:04:40,670 --> 00:04:44,450 Whenever we are moving one disc we are having a print statement. 73 00:04:44,450 --> 00:04:44,780 Again. 74 00:04:44,780 --> 00:04:46,940 Remember that's one of the conditions in the question. 75 00:04:46,940 --> 00:04:49,400 We can only move one disc at a time. 76 00:04:49,400 --> 00:04:55,610 So whenever we are having a recursive call inside the recursive call, whenever we reach the case where 77 00:04:55,610 --> 00:04:59,300 we are dealing with one disc, we are having a print statement. 78 00:04:59,300 --> 00:05:03,830 Now let's complete this branch of the recursion tree as well. 79 00:05:04,370 --> 00:05:05,750 Let's make some space. 80 00:05:06,740 --> 00:05:12,290 So over here we want to move two disks, these two disks from row two to row three. 81 00:05:12,320 --> 00:05:19,100 Now because n at this place is more than one we are going to move n minus one disks which is one disk 82 00:05:19,100 --> 00:05:21,680 from rod two to rod one. 83 00:05:21,680 --> 00:05:28,490 And after that we are going to move the nth disk or disk two from rod two to rod three. 84 00:05:29,630 --> 00:05:37,610 And after that we are moving these n minus one disks or one rod from rod one, because they are at rod 85 00:05:37,610 --> 00:05:38,630 one at this point. 86 00:05:38,630 --> 00:05:41,150 And the final destination for it is rod three. 87 00:05:41,150 --> 00:05:46,370 So we are going to move them from rod one to rod three, and rod two is going to be the auxiliary or 88 00:05:46,370 --> 00:05:47,570 helper rod. 89 00:05:47,570 --> 00:05:52,640 So this is how we will solve this question again inside this recursive call. 90 00:05:52,640 --> 00:05:58,460 Because n at this point is one we are going to have a print statement to move disk one from rod two 91 00:05:58,490 --> 00:05:59,300 to rod one. 92 00:05:59,300 --> 00:06:03,890 And over here also, because we have just one disk, we are going to have a print statement to move 93 00:06:03,890 --> 00:06:06,950 disk one from rod one to rod three. 94 00:06:06,950 --> 00:06:10,580 So these are all the print statements that we will have. 95 00:06:10,580 --> 00:06:13,610 Notice that we will have seven print statements. 96 00:06:14,330 --> 00:06:18,140 Now let's also quickly think whether this will actually work. 97 00:06:18,140 --> 00:06:19,520 So let's think about this. 98 00:06:19,520 --> 00:06:24,410 So first over here we are going to move rod one to rod three. 99 00:06:24,410 --> 00:06:26,720 So let's just write that over here okay. 100 00:06:26,720 --> 00:06:29,570 So we have rod one over here. 101 00:06:31,800 --> 00:06:33,930 We have rod two over here. 102 00:06:34,980 --> 00:06:37,560 And we have brought three over here. 103 00:06:37,560 --> 00:06:42,960 Let's just see whether this call will actually achieve this desired state. 104 00:06:42,960 --> 00:06:48,060 So initially we're going to move disk one from road one to road three. 105 00:06:48,060 --> 00:06:50,490 So we're going to have disk one over here. 106 00:06:50,490 --> 00:06:52,170 And disk one is the green one. 107 00:06:52,170 --> 00:06:54,300 So let me probably write it as green. 108 00:06:55,170 --> 00:06:57,780 For us to relate to this diagram over here. 109 00:06:57,780 --> 00:06:59,910 So we're going to have the green disk over here. 110 00:06:59,910 --> 00:07:06,450 And after that we're going to execute this print statement over here which is move disk two which is 111 00:07:06,450 --> 00:07:08,820 the blue disk from rod one to row two. 112 00:07:08,850 --> 00:07:10,650 So the blue one is going to be over here. 113 00:07:10,650 --> 00:07:11,640 And over here. 114 00:07:11,640 --> 00:07:15,210 We are going to have move disk one from rod three to row two. 115 00:07:15,240 --> 00:07:18,960 So the green over here is going to be moved from rod three to rod two. 116 00:07:18,990 --> 00:07:20,970 So the green disk is going to be over here. 117 00:07:20,970 --> 00:07:26,760 And notice that we have achieved this arrangement where green is on top and you have blue below it. 118 00:07:26,760 --> 00:07:28,380 And that's what you can see over here. 119 00:07:28,380 --> 00:07:32,490 So notice this part over here has achieved this. 120 00:07:32,490 --> 00:07:38,190 And after that over here we are moving disk three which is orange from rod one to rod three. 121 00:07:38,190 --> 00:07:40,290 So that should be pretty straightforward. 122 00:07:40,290 --> 00:07:45,450 So we have orange over here and over here again in this call. 123 00:07:45,450 --> 00:07:51,600 Let's see whether these two disks are moved from rod to to rod three achieving this desired state. 124 00:07:51,600 --> 00:07:57,870 So initially we're going to move disk one from row two to rod one and disk one. 125 00:07:58,990 --> 00:07:59,920 Is the green one. 126 00:07:59,920 --> 00:08:02,110 So the green one is going to be moved over here. 127 00:08:02,720 --> 00:08:06,410 And over here we have disc two, which is the blue one. 128 00:08:06,410 --> 00:08:10,010 The blue one is going to be moved from rod two to rod three. 129 00:08:10,010 --> 00:08:12,020 So the blue one comes over here. 130 00:08:12,260 --> 00:08:19,340 And over here we have disc one which is the green one from round one to round three, round one to rod 131 00:08:19,340 --> 00:08:19,700 three. 132 00:08:19,700 --> 00:08:21,680 So the green one comes over here. 133 00:08:21,680 --> 00:08:28,730 And notice that we have achieved green blue orange green blue orange which was the desired order. 134 00:08:28,730 --> 00:08:31,370 And these are now at rod three. 135 00:08:31,370 --> 00:08:33,170 So yes our function is working. 136 00:08:33,170 --> 00:08:38,360 And this is the recursion tree of the approach to solve the Tower of Hanoi problem.