A Trick to trace tower of Hanoi manually

• What procedure suggests:               

         If n=1 move the disk from source to destination.

         Otherwise

(i) Move n-1 disks from source to temp.  peg by using destination peg as  auxiliary.

(ii)Move n^th  disk from temp. to destination then move n-1 disks using source peg as c   auxiliary.

• An alternative for easy manual tracing.

           Construct a tree a shown in fig.

         (I) If n!=1then lftchild ={n-1,S,D,T} and rtchild={n-1,T,S,D}

         Do this till n=1;

         For n=3 you will get tree as shown in fig. to get moves go for inorder traversal of tree,

         ( Move n^th disk from source to destination.{n, s, t, d} )  

Inorder Traversal
1. Traverse the left sub tree in inorder.  
2. Visit the root.
3. Traverse the right sub tree in inorder.

Do the Inorder traversal for the above problem   

Move disk 1 from A to C.

Move disk 2 from A to B.

Move disk 1 from C to B.

Move disk 3 from A to C.

Move disk 1 from B to A.

Move disk 2 from B to C.

Move disk 1 from A to C.