PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q5(b)

Data Structure and Algorithms · 3 marks

Open in the Padhaiko app

Topic: Recursion

Question

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:

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:

  1. Move Disk 1 from
  2. Move Disk 2 from
  3. Move Disk 1 from
  4. Move Disk 3 from
  5. Move Disk 1 from
  6. Move Disk 2 from
  7. Move Disk 1 from
  8. Move Disk 4 from (Center move at root)
  9. Move Disk 1 from
  10. Move Disk 2 from
  11. Move Disk 1 from
  12. Move Disk 3 from
  13. Move Disk 1 from
  14. Move Disk 2 from
  15. Move Disk 1 from
Answer:

The recursion tree for disks has depth 4 and exactly move nodes executed via in-order traversal:

All 4 disks are transferred from to in exactly 15 valid steps.

All past exam questions for Data Structure and Algorithms