Past exam question: 2079 Ashwin (Back), Q5(b)
Open in the Padhaiko appQuestion
Construct a recursion tree for TOH problem with 4 disks.
Solution
Total Move Count and Recursive Expansion: For disks, moving from Source () to Destination () using Auxiliary ():
The root call is TOH(4, S, D, A). Each node TOH(k, src, dest, aux) decomposes into:
- Left subtree:
TOH(k - 1, src, aux, dest) - Center move: Move disk from
srctodest - Right subtree:
TOH(k - 1, aux, dest, src)
Decomposition of the Recursion Tree (Levels 0 to 2):
Level 0: TOH(4, S, D, A)
/ | \
--------------------- | ---------------------
/ | \
Level 1: TOH(3, S, A, D) [Move 4: S->D] TOH(3, A, D, S)
/ | \ / | \
--- | --- --- | ---
/ | \ / | \
L2: TOH(2,S,D,A) [3:S->A] TOH(2,D,A,S) TOH(2,A,S,D) [3:A->D] TOH(2,S,D,A)Complete Recursion Tree Down to Base Cases (): Expanding every TOH(2, ...) node into two TOH(1, ...) leaf calls produces all 15 discrete moves in in-order execution sequence:
TOH(4, S, D, A)
/ | \
-------------------- | --------------------
/ | \
TOH(3, S, A, D) [Move 4: S->D] TOH(3, A, D, S)
/ | \ (8) / | \
---- | ---- ---- | ----
/ | \ / | \
TOH(2,S,D,A) [3:S->A] TOH(2,D,A,S) TOH(2,A,S,D) [3:A->D] TOH(2,S,D,A)
/ | \ (4) / | \ / | \ (12) / | \
/ | \ / | \ / | \ / | \
T1 [2] T1 T1 [2] T1 T1 [2] T1 T1 [2] T1
(1) S->D (3) (5) D->A (7) (9) A->S (11) (13) S->D (15)
(2) (6) (10) (14)
*(where each represents a base call `TOH(1, src, dest, aux)` executing a move of Disk 1)*Chronological Sequence of 15 Moves:
- Move Disk 1 from
- Move Disk 2 from
- Move Disk 1 from
- Move Disk 3 from
- Move Disk 1 from
- Move Disk 2 from
- Move Disk 1 from
- Move Disk 4 from (Center move at root)
- Move Disk 1 from
- Move Disk 2 from
- Move Disk 1 from
- Move Disk 3 from
- Move Disk 1 from
- Move Disk 2 from
- Move Disk 1 from
Answer:
The recursion tree for disks has depth 4 and exactly move nodes executed via in-order traversal:
- Left subtree
TOH(3, S, A, D)executes moves 1 through 7. - Root move executes move 8: Move disk 4 from .
- Right subtree
TOH(3, A, D, S)executes moves 9 through 15.
All 4 disks are transferred from to in exactly 15 valid steps.