---
title: "Box trace and TOH recursion tree"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:box-trace-toh-tree"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/box-trace-toh-tree
site: BCT Engineering
---

# Box trace and TOH recursion tree

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2071 Magh, 1+3 marks
- Video: [tower of hanoi in data structure |tower of hanoi 3 disks algorithm| tower of hanoi 3 disks solution](https://www.youtube.com/watch?v=UOPHbANFa3w) — Intelligent Competitor
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/box-trace-toh-tree
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

What is box trace? Construct a recursion tree for tower of Hanoi problem consisting of 3 disks.

## Short answer

A box trace is a manual tool for tracing recursive functions by drawing each call as a box with parameters, local variables, and return value, linked to show the activation stack. For Tower of Hanoi with 3 disks, the recursion tree has root TOH(3,A,C,B) and yields the 7 moves: A→C, A→B, C→B, A→C, B→A, B→C, A→C.

## Answer

#### Box trace
A box trace is a manual tool for tracing recursive functions. Every call is drawn as a box holding the function's parameters, local variables, a return address (label) and the return value. When a function calls itself, a new box is drawn and linked to the caller's box by an arrow. When a call finishes, its box is crossed out and control goes back to the label in the caller's box. It shows the run-time stack of activation records.

Example for `fact(3)`:

```text
fact(3): n=3, returns 3*fact(2)
   fact(2): n=2, returns 2*fact(1)
      fact(1): n=1, returns 1
```
The innermost box returns 1, then 2 and finally 6.

#### Recursion tree for Tower of Hanoi (3 disks)
`TOH(n, from, to, aux)`: move n−1 disks from→aux, move disk n from→to, move n−1 disks aux→to.

Let the pegs be A (source), C (destination), B (auxiliary).

```text
              TOH(3,A,C,B)
            /      |       \
   TOH(2,A,B,C)  A->C   TOH(2,B,C,A)
    /    |    \            /    |    \
 T(1)  A->B  T(1)       T(1)  B->C  T(1)
A,C,B       C,B,A      B,A,C       A,C,B
  |           |           |           |
 A->C        C->B        B->A        A->C
```
T(1) = TOH(1, from, to, aux) is a leaf: it just moves one disk. Reading the moves from left to right gives the 7 moves (2³ − 1):


1. A→C (disk 1)
2. A→B (disk 2)
3. C→B (disk 1)
4. A→C (disk 3)
5. B→A (disk 1)
6. B→C (disk 2)
7. A→C (disk 1)

The tree has 7 calls (1 + 2 + 4), each producing exactly one move, and its height is 3. Total moves T(n) = 2T(n−1) + 1 = 2ⁿ − 1.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a box trace?
   A. A compiler optimization
   B. A type of loop
   C. A manual tool drawing each call as a box with parameters, locals, return address and value
   D. A stack overflow error
   Answer: C. It shows the run-time stack of activation records. (Key point: Box trace)

2. What happens to a box when its call finishes?
   A. A new box is drawn
   B. It is merged
   C. The program ends
   D. It is crossed out and control returns to the label in the caller's box
   Answer: D. Control goes back to the caller. (Key point: Finished call)

3. How many calls does the TOH tree for 3 disks have and what is its height?
   A. 7 calls, height 3
   B. 8 calls, height 3
   C. 3 calls, height 7
   D. 7 calls, height 7
   Answer: A. 1 + 2 + 4 = 7 nodes, 3 levels. (Key point: Tree size)

4. What is the recurrence for TOH moves?
   A. T(n) = T(n-1) + 1
   B. T(n) = 2T(n-1) + 1 = 2^n - 1
   C. T(n) = 2T(n/2)
   D. T(n) = n^2
   Answer: B. Two sub-tower moves plus one disk move. (Key point: Recurrence)

## Related in Data Structure and Algorithm

- [Recursion tree for Tower of Hanoi, 4 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-recursion-tree-4-disks) — Data Structure and Algorithm, chapter 5
- [Tree recursion and TOH with n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atree-recursion-toh-algorithm) — Data Structure and Algorithm, chapter 5
- [TOH for 3 disks and recursion principle](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-tree-principle) — Data Structure and Algorithm, chapter 5
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — Data Structure and Algorithm, chapter 5, asked 2×
- [Solve TOH for 3 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-steps) — Data Structure and Algorithm, chapter 5, asked 2×

## Related in other subjects

- [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — Discrete Structure, chapter 3
- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3
- [Dispersion measures; construct box plot](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Aabsolute-relative-dispersion-box-plot) — Probability and Statistics, chapter 1