Data Structures and Algorithms - Old Questions

4. State TOH problem. Write recursion tree when no. of disks are four.

5 marks | Asked in 2069

Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.



Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Recursion Tree for TOH

1. Move Tower(N-1, BEG, END,AUX)

2. Move Tower(1, BEG, AUX, END) à(BEG à END)

3. Move Tower (N-1, AUX, BEG, END)


Recursion Tree when no. of disks are 4 as: