DSA Tracker

Visualize

Tower Of Hanoi

Move n-1 out of the way, move the biggest, move n-1 back on top

time O(2^n)space O(n)

To move n disks from A to C, first move the top n-1 disks from A to B (out of the way), then move the single biggest disk from A straight to C, then move those n-1 disks from B onto C. Each smaller sub-tower is solved the same recursive way, producing exactly 2^n - 1 moves.

Details

Animated on: n = 3 disks, peg A (source) → peg C (target), using peg B (auxiliary).

Problem:Tower Of HanoiMedium

Move n-1 out of the way, move the biggest, move n-1 back on top

step 1 / 9

321
[0]
[1]
[2]

3 disks stack on peg A (largest at bottom). 2^3 - 1 = 7 moves will move them all to peg C.

  • A=0· arr[0] = 321
Pseudocode
1FUNCTION hanoi(n, from, aux, to):
2  IF n is 0: RETURN
3  hanoi(n-1, from, to, aux)   (move the top n-1 disks out of the way)
4  move disk n from the source peg to the target peg
5  hanoi(n-1, aux, from, to)   (move those n-1 disks onto the target)
6  (total moves = 2^n - 1)

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. 3 disks stack on peg A (largest at bottom). 2^3 - 1 = 7 moves will move them all to peg C.
  2. Move 1: disk 1, A → C.
  3. Move 2: disk 2, A → B.
  4. Move 3: disk 1, C → B.
  5. Move 4: disk 3, A → C — the biggest disk, finally free to move.
  6. Move 5: disk 1, B → A.
  7. Move 6: disk 2, B → C.
  8. Move 7: disk 1, A → C.
  9. All 7 moves complete (2^3 - 1 = 7). Every disk now sits on peg C, in order, largest at bottom.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Tower Of Hanoi in the editorAll Recursion problemsBack to roadmap