A Unified Implementation of Tree Traversals

Summary: As of version 2.0, JDSL provides three iterator classes to iterate over the nodes of a tree, and one template algorithm class to walk an Euler Tour. We discuss a class that combines iterators and algorithm into a single iterator class, adding capabilities to

• combine several traversal orders into one iterator
• perform a generalized inorder traversal on jdsl.core.api.InspectableTrees
• customize traversals
• carry out single traversal steps

Package jdsl.core.ref contains three classes to iterate over the nodes of an InspectableTree, PreOrderIterator, InOrderIterator, and PostOrderIterator. These classes implement the interface PositionIterator and differ notably only in their definition of a private method traverse, which traverses a node and recursively calls itself on the node's children, in order depending on the kind of traversal to be performed. Moreover, package jdsl.core.algo.traversals consists of class EulerTour, which does not implement PositionIterator, but is an abstract template implementation of an Euler Tour that can be customized by overriding some otherwise empty methods, like visitFirstTime(Position).

Given the conceptually similar behavior of all of these classes, they can be combined into one class that is a common generalization, i.e. that can be used like any of them while providing features not present in all of them. As an alternative solution we hence define a class TreeTraversal implementing PositionIterator and expecting the particular traversal order in its constructor. You may want to take a look at the source code while continuing to read.

Specifying a traversal order. Besides a tree to traverse, the constructor expects an integer specifying a particular order of traversal. We defined class constants PRE_ORDER, IN_ORDER, POST_ORDER, and EULER_TOUR with the obvious meaning. In addition, traversal orders can be combined by passing sums of these constants. E.g., a combined pre- and postorder traversal can be specified as PRE_ORDER + POST_ORDER. Examples of different traversal orders are provided in the output of the main method; simply execute java jdslx.core.algo.traversals.TreeTraversal. Note that EULER_TOUR differs from PRE_ORDER + IN_ORDER + POST_ORDER in the number of visits at leafs.

Generalized inorder traversal of InspectableTrees. Instead of restricting an inorder traversal to InspectableBinaryTrees, we generalize it to visit an internal node each time a subtree that is not rightmost has been traversed (see the output again).

Adding custom behavior. EulerTour and other template implementations in the JDSL, empty methods are provided that can be overridden to add custom behavior during a traversal. This is useful, for example, to evaluate an expression represented in an expression tree while printing it.

Single traversal steps. Class methods allow traversing a tree one step at a time. Useful for dynamic trees and partial traversals. Leaves execution control to the class requiring a step rather than having TreeTraversal perform a complete traversal while occasionally calling a template method. Note that the inorder predecessor of a node is in general not unique in an InspectableTree, so that a InspectableBinaryTree is expected instead. This ambiguity could be eliminated by requiring an additional parameter.

Conclusion. The present unification of traversal iterators and the Euler Tour algorithm reduces code duplication and thus reduces maintenance cost. It adds useful extra behavior at essentially no cost on the implementation level. However, it's use is slightly more complicated to understand and syntactically less convenient. The latter problem can be circumvented by defining classes PreOrderIterator and so on that simply instantiate the appropriate version of TreeTraversal.

• TreeTraversal.java