Tree Traversal/Traversal Method Template

Notes

In the process of implementing tree traversals, it is useful to implement a method template pattern for the Tree or Graph object that allows us to re-use our traversal algorithm to perform arbitrary functions.

The template method pattern is a generic computation mechanism that is customized for a particular application by using a function called a hook.

To make this more concrete, when we perform an Graphs/Euler Tour of a tree, we visit each vertex twice as we make a circuit of the entire tree. An Euler tour can be thought of as a generalization of the Trees/Preorder and Trees/Postorder traversal, as it performs both.

To use the template method pattern for an Euler tour, then, we define a pre-visit hook, which is a function that is run when we first arrive at a vertex and before we have visited any of its ancestor nodes, and a post-visit hook, which is a function that is run after we have visited all of the vertex's ancestor nodes.

OOP Code Design

The template for doing this is to create an Euler Tour class that stores a reference to a tree (takes a tree argument in its constructor).

The Euler Tour class defines a pre-visit hook function, which is by default an empty method, and a post-visit hook function, which is also by default an empty method. These methods both take two arguments: a position in the tree, and the level of that position in the tree. (These are quantities that are known during the Euler Tour, see below). To customize the behavior of the Euler Tour, we can extend the Euler Tour class, and simply redefine the pre-visit and post-visit hook functions to do whatever we would like.

To perform an Euler tour, we define a recursive, private tour function for the Euler Tour class, which takes as an argument the node to visit and its level in the tree. We then define another, public executeTour method that calls the private tour function, and passes it the root node and the level of the root node (0).

The structure of the tour method is as follows:

• Run the pre-visit hook function (pass it the current position in the tree and level of the current position in the tree
• For each child of the current position:
  • Recur on the child's subtree (call tour method on child)
  • Update any paths being tracked
• Perform the post-visit hook function (pass it the current position in the tree and the level of the current position in the tree)