Recursion tree for Tower of Hanoi, 4 disks

Using TOH(n, from, to, aux) with the call TOH(4, A, C, B), each call makes two calls for n-1 disks and moves disk n between them.

TOH(4,A,C,B)                         [move 8: disk 4 A->C]
├─ TOH(3,A,B,C)                      [move 4: disk 3 A->B]
│  ├─ TOH(2,A,C,B)                   [move 2: disk 2 A->C]
│  │  ├─ TOH(1,A,B,C)                [1: disk 1 A->B]
│  │  └─ TOH(1,B,C,A)                [3: disk 1 B->C]
│  └─ TOH(2,C,B,A)                   [move 6: disk 2 C->B]
│     ├─ TOH(1,C,A,B)                [5: disk 1 C->A]
│     └─ TOH(1,A,B,C)                [7: disk 1 A->B]
└─ TOH(3,B,C,A)                      [move 12: disk 3 B->C]
   ├─ TOH(2,B,A,C)                   [move 10: disk 2 B->A]
   │  ├─ TOH(1,B,C,A)                [9: disk 1 B->C]
   │  └─ TOH(1,C,A,B)                [11: disk 1 C->A]
   └─ TOH(2,A,C,B)                   [move 14: disk 2 A->C]
      ├─ TOH(1,A,B,C)                [13: disk 1 A->B]
      └─ TOH(1,B,C,A)                [15: disk 1 B->C]

Structure: root, 2 children, 4 grandchildren, 8 leaves.

Facts about the tree (checked with a program):

• Levels: 4 (n = 4, 3, 2, 1), with 1, 2, 4, 8 nodes.
• Total calls = 2⁴ − 1 = 15, so there are 15 moves.
• Moves are made in in-order sequence: 1 to 15 as numbered above.
• Move sequence: 1:D1 A→B, 2:D2 A→C, 3:D1 B→C, 4:D3 A→B, 5:D1 C→A, 6:D2 C→B, 7:D1 A→B, 8:D4 A→C, 9:D1 B→C, 10:D2 B→A, 11:D1 C→A, 12:D3 B→C, 13:D1 A→B, 14:D2 A→C, 15:D1 B→C.