Visitor pattern lacking parameters

Question

I'm sure this must be a common problem with the Visitor pattern, so thought I'd see if there is a standard solution.

How can you re-code a tree traversal where the methods are built into the tree classes themselves, say

class Node {
    void Traverse(SomeType& t) { ... }
};

into code that uses a visitor. Two solutions that come to mind are either

class Visitor {
    stack<SomeType> argumentStack;

    void Visit() {
        // do work, add new arguments onto stack
        // call accept() on child objects
        // pop stack
    }
};

or adding the arguments to the accept(Visitor&) and visit() methods themselves. But then this is no better than the original traversal built into the classes.

As a further problem, what happens if each of the built in traversal methods take different arguments, or some return values and others don't, or they don't all return the same types?