Due April 26, 1999 before class

Read about continuations and continuation-passing style.

You are given a binary tree with three special kinds of nodes: milestones, devils, and angels. You are to traverse the binary tree in pre-order, printing the nodes in the order you visit them subject to the following constraints. If you encounter a devil, you must jump back to the latest milestone and continue traversing the tree as if you had just finished traversing the subtree rooted at the milestone. This means that the jump does not constitute a visit to the milestone node since we are traversing the tree in pre-order. If another devil, or maybe even the same devil, is subsequently encountered, you must jump back to the penultimate milestone, not to the one just used. In other words, each milestone can be returned to exactly once; a succession of devils pushes the computation back to earlier and earlier stages. An angel sends the computation to where it was when it most recently encountered a devil. Again when you jump to a devil node, you should resume traversing the tree as if you had just finished traversing the subtree rooted at the devil. A succession of angels pushes the computation forward to more advanced states. If a devil (or angel) is encountered with no milestone (or devil) remaining, the devil (or angel) has no effect. To recharge any milestone, you must revisit it. There is no non-determinism, just backtracking.

Your solution must be in Java. I recommend writing a solution in continuation-passing style.

Sample input:

                         1
                   /           \
                2                  3
             /     \           /       \
    4(Milestone)     5        6         7
    /      \      /      \
 8(Devil)   9   10(Angel) 11

1
2
4
8
5 
10 
9 
5
10
11
3
6
7