posted 10 years ago
Think of the calls to relocate() in a tree form, the output is in the following order Child->Parent->Child this means that the root of the tree doesn't produce output until it's left child has finished.
The function calls itself twice, which means each node has two children (except the leaves) and the depth of the tree is 3 since n is decremented by 1 each time.
This means that the depth is 3, number of children of each node (except the leaves) is 2 and the total number of nodes is 7. (hence the number of lines in output)
The first time relocate() is called it doesn't output anything until it's first child has finished (a true depth-first order tree would wait for all its children to finish), this is true for all nodes in the tree.
The tree looks like this
1. relocate(3,'A','B','C') -> "relocate slice 3 from A to C"
2. ->relocate(2,'A','C','B') -> "relocate slice 2 from A to B"
3. ->->relocate(1,'A','B','C') -> "relocate slice 1 from A to C"
4. ->->relocate(1,'C','A','B') -> "relocate slice 1 from C to B"
5. ->relocate(2,'B','A','C') -> "relocate slice 2 from B to C"
6. ->->relocate(1,'B','C','A') -> "relocate slice 1 from B to A"
7. ->->relocate(1,'A','B','C') -> "relocate slice 1 from A to C"
the -> denotes the depth in the tree, the order of the output is 3,2,4,1,6,5,7 (Child->Parent->Child)