TOH algorithm and recursion tree

Algorithm TOH(n, from, to, aux)

1. If n = 1: move disk 1 from from to to; return.
2. TOH(n-1, from, aux, to).
3. Move disk n from from to to.
4. TOH(n-1, aux, to, from).

#include <stdio.h>

/* move n disks from 'from' to 'to' using 'aux' */
void toh(int n, char from, char to, char aux) {
    if (n == 1) {                                   /* base case */
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    toh(n - 1, from, aux, to);                      /* step 1 */
    printf("Move disk %d from %c to %c\n", n, from, to);   /* step 2 */
    toh(n - 1, aux, to, from);                      /* step 3 */
}

int main(void) {
    toh(3, 'A', 'C', 'B');
    return 0;
}

All solution steps for three disks (call TOH(3, A, C, B))

Output (verified by running the algorithm):

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Recursion tree for 3 disks

Each node is a call TOH(n, from, to, aux). A move is performed at each node between its left and right subtree calls.

                    TOH(3,A,C,B)
                  [4: disk 3 A->C]
              /                      \
     TOH(2,A,B,C)                TOH(2,B,C,A)
    [2: disk 2 A->B]            [6: disk 2 B->C]
      /         \                 /         \
 (1,A,C,B)   (1,C,B,A)      (1,B,A,C)   (1,A,C,B)
 [1: A->C]   [3: C->B]      [5: B->A]   [7: A->C]

Moves are printed in in-order (left subtree, node, right subtree): 1 to 7.

The tree has 2³ − 1 = 7 nodes, so 7 moves are made. Number of calls for n disks = 2ⁿ − 1, and the depth of the tree is n.