Is this higher order function any use at all without relying on a side-effect?
The answer to this question is obviously no, since the function returns always nil.
The general question I'm seeking to explore here is the purity or non-purity of higher order functions in practical use cases (and hence, how to use them well).
I'm not sure to understand what ...
Firstly, is there a name for this variant of the visitor pattern?
You have made what I like to call the inviting visitor pattern. I'm not sure this pattern is common, but I have seen it before, disguised and usually involves 3 (types of) classes instead of 2, each with their own concern.
inviter: let visitee invite visitor
visitee: let visitor ...
the typical operations like mapcar or reduce - which return a value - could also be provided in similar fashion for trees.
Note also that your function is not tail recursive and may cause a stack overflow...