Design for a tree using a visitor pattern, how to implement different kinds of traversal?

Question

I've been asked a theoretical design question with an eye upon the GoF patterns.:

"Given a design for a tree using a standard visitor pattern, how would your design look to allow a user to choose between om pre-order, in-order or post-order traversals?"

I'm thinkin of just letting the visitor be, but give the traversal over to an Iterator object following the Iterator Pattern.

The idea would be to implement 3 iterators that enable the desired traversal. They have an interface and the Visitor only needs to interact with this interface, giving itself as an argument to the iterator which provides traversal. The user can choose which iterator to use when giving one to the visitor.

Does this sound like an elegant solution? Any better ideas?

Answer 1

One thing about Visitor Patterns is misconception, that it is somehow tied to tree-like structure. Which is quite wrong. The question sounds as if it was doing just that. So first thing would be fixing this misconception. And then I would exactly like you said. Create 3 different iterators one for each type of traversal.

But this depends on complexity of the tree. If each node has same specified collection of children, then it is easy. The problems start when different types of nodes have different structure of children. Then visitor starts making sense. But the different types of traversal order stop making a sense, because they only work for n-arry trees, not for trees with arbitrary types of children in each node.

Answer 2

Maybe I'm missing something but don't you simply need different visitors for each of the traversal types, PreOrderTreeVisitor, InOrderTreeVisitor, PostOrderTreeVisitor with the visit method specific to the type of traversal. Probably you want them to take some action that could be applied to a node so that they, in effect, become the iterators over the tree.

interface ITreeVisitor {
   void visit(ITreeNode node);
}

interface ITreeNode {
   ITreeNode getLeft();
   ITreeNode getRight();
   int getValue();
   void accept(ITreeVisitor visitor);
}

interface IAction {
   void do(ITreeNode);
}

class TreeNode implements ITreeNode {
   ...
   public void accept(ITreeVisitor vistor) {
      visitor.visit(this);
   }
}

class PreOrderTreeVisitor implements ITreeVisitor {

   private IAction action;

   public PreOrderTreeVisitor(IAction action) {
        this.action = action;
   }

   public void visit(ITreeNode node) {

       action.do(node);

       ITreeNode left = node.getLeft();
       if (left != null) left.accept(this);

       ITreeNode right = node.getRight();
       if (right != null) right.accept(this);
   }
}