Package io.openml.gearbox.binarytree

Class AbstractInOrderTraversalVisitor<T>

java.lang.Object
io.openml.gearbox.binarytree.AbstractInOrderTraversalVisitor<T>
Type Parameters:
T - The type of value wrapped in the Visitable object to be visited by this visitor. For example, if the visitable class is ImmutableTreeNode, then the type of value is the return type of its ImmutableTreeNode.getValue() method
All Implemented Interfaces:
Visitor<T>
public abstract class AbstractInOrderTraversalVisitor<T> extends Object implements Visitor<T>
An abstract Visitor that performs a non-recursive (iterative) in-order traversal of a binary tree.

Subclasses must implement the processNode(TreeNode) method to define what action to take on each node. This class uses the Template Method pattern, where the traversal algorithm is the template and the node processing is the customizable step.

Compared with TreeTraverser.traverseInOrder(TreeNode, Visitor), this visitor is assumed to be visiting the entire tree and uses a very common and practical adaptation where the traversal logic is bundled inside the visitor. The client just needs to kick it off by calling the Visitable.accept(Visitor) on the root node. The reason for this common adaptation is for convenience. It simplifies the client code and encapsulates the traversal algorithm withi the operation that depends on it.

AbstractInOrderTraversalVisitor and TreeTraverser.traverseInOrder(TreeNode, Visitor) reflect the classic architectural trade-off between convenience and flexibility where the former is favored by AbstractInOrderTraversalVisitor. Their core difference lies in the separation of responsibilities. The TreeTraverser.traverseInOrder(TreeNode, Visitor) separates the how (the traversal algorithm) from the what (the operation performed on a node). The AbstractInOrderTraversalVisitor model combines them.

Using AbstractInOrderTraversalVisitor is simpler for a single, specific task. The user only needs to instantiate one object and make one call: root.accept(new PrintingVisitor()). It's a winner for simplicity.

In terms of flexibility and reusability, however, this model is rigid. If we want to perform the exact same printing operation but in a pre-order traversal, we would need to create a whole new PreOrderPrintingVisitor class. This would require duplicate the printing logic, violating the "Don't Repeat Yourself" (DRY) principle. The traversal algorithm and the node operation are permanently coupled.

  • Constructor Details

    • AbstractInOrderTraversalVisitor

      public AbstractInOrderTraversalVisitor()

  • Method Details

    • processNode

      protected abstract void processNode(TreeNode<T> node)
      An abstract method that defines the "visit" operation to be performed on each node during the traversal.

      This is the customizable step in the template method. Although this abstract method introduces a layer of flexibility, it does not achieve the same level of architectural decoupling and reusability as the TreeTraverser.traverseInOrder(TreeNode, Visitor) model. The key difference lies in what is being coupled:

      We are coupling the action, i.e. this method, to a specific traversal algorithm (in-order). If we, for example, create a SummingVisitor that extends AbstractInOrderTraversalVisitor, its summing logic is now permanently tied to an in-order traversal. If we later need to sum the nodes using a pre-order traversal, we would have to create an entirely new class that extends AbstractPreOrderTraversalVisitor abstract class and a new PreOrderSummingVisitor that duplicates the summing logic. The action is not reusable across different traversal strategies. In the end, having 2 visitors (PrintingVisitor, SummingVisitor) with pre-order, in-order, and post-order capabilities would require client to maintain 2 x 3 = 6 classes of source code.

      Parameters:
      node - The node to process

    • visit

      public void visit(ImmutableTreeNode<T> node)
      Description copied from interface: Visitor
      Visits an ImmutableTreeNode.
      Specified by:
      visit in interface Visitor<T>
      Parameters:
      node - The ImmutableTreeNode to visit.

    • visit

      public void visit(MutableTreeNode<T> node)
      Description copied from interface: Visitor
      Visits a MutableTreeNode.
      Specified by:
      visit in interface Visitor<T>
      Parameters:
      node - The MutableTreeNode to visit.