L2 · Working engineerRecursion~8 min · 6 tests#54

Tower of Hanoi in Python

Solve the Tower of Hanoi recursively, return every move, and prove the 2ⁿ − 1 move count. A classic recursion interview question, run live.

The problem

Return the list of moves that transfers n disks from peg "A" to peg "C" using "B" as the spare. Each move is a tuple (from_peg, to_peg).

A larger disk may never sit on a smaller one. For n = 3 there are 7 moves.

Examples

Example 1
Input
```
len(hanoi(3))
```
Expected output
```
7
```

Example 2

Input

hanoi(2)

Expected output

[('A', 'B'), ('A', 'C'), ('B', 'C')]

+ 4 hidden tests on Submit — the largest disk moves in the middle.

Edge cases to ask about

n = 0
n = 1

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · hanoi

def hanoi(n, source="A", target="C", spare="B"):
    """Return the list of (from, to) moves."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Recursive three-step plan	O(2ⁿ)	O(n) stack + O(2ⁿ) output	Move n−1 out of the way, move the largest, move n−1 back on top.

Walkthrough of the optimal approach (try it yourself first)

Three steps: move n − 1 disks from source to spare (using target as the helper), move disk n to target, move the n − 1 disks from spare to target (using source as the helper).

The recurrence T(n) = 2T(n − 1) + 1 gives 2ⁿ − 1 moves — exponential, and provably optimal.

Complexity: O(2ⁿ) time, O(n) space. T(n) = 2·T(n−1) + 1 solves to 2ⁿ − 1 moves; the recursion is only n frames deep (the move list itself is 2ⁿ − 1 long).

Reveal the reference solution

def hanoi(n, source="A", target="C", spare="B"):
    if n == 0:
        return []
    return (hanoi(n - 1, source, spare, target)
            + [(source, target)]
            + hanoi(n - 1, spare, target, source))

Follow-ups interviewers ask

Prove 2ⁿ − 1 is the minimum.
Print moves without storing them (O(n) memory).

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Tower of Hanoi in Python?

The optimal solution runs in O(2ⁿ) time and O(n) auxiliary space. T(n) = 2·T(n−1) + 1 solves to 2ⁿ − 1 moves; the recursion is only n frames deep (the move list itself is 2ⁿ − 1 long).

What follow-up questions do interviewers ask about Tower of Hanoi in Python?

Prove 2ⁿ − 1 is the minimum. Print moves without storing them (O(n) memory).