skip to content

In a Visitor-based design over a tree, who should own the traversal — the elements' accept methods, the visitor itself, or a separate iterator — and what are the consequences of each choice?

level: seniorimportance: should knowfreq 25%

answer

  1. Three owners: element accept, visitor, external walker
  2. Visitor-driven = pruning, early exit, return values
  3. BaseVisitor with default full walk = best of both
  4. ANTLR: Visitor (you recurse) vs Listener (walker recurses)
  5. Cycles/DAGs need a visited set in the driver

basics

~20 s

Traversal can live in the element's accept (elements recurse into children), in the visitor (each visit method recurses), or in a separate walker object. Putting it in the visitor gives the most control — you can change order, skip subtrees, or stop early.

solid answer

~50 s

Three options. (1) **Element-driven**: `accept` visits the node then recurses into children. Simplest, guarantees full coverage, but hard-codes one order and gives visitors no way to prune or short-circuit. (2) **Visitor-driven**: `accept` only calls `visit(this)`, and each `visit` method explicitly recurses into the children it cares about. Maximum control — pre/post/in-order, skipping subtrees, early exit, depth tracking, scope push/pop for symbol tables — at the cost of repeating traversal logic in every visitor (usually solved with an abstract `BaseVisitor` implementing the default full walk, which concrete visitors override selectively). (3) **External walker/iterator**: a separate object walks and calls `element.accept(v)` per node, decoupling order from both hierarchies and letting you swap DFS/BFS or parallelize, but it must know the child structure, which weakens element encapsulation. Production compilers overwhelmingly use option 2 with a base visitor, because passes genuinely need order control, pruning, and contextual state. ANTLR ships both: `Visitor` (you recurse) and `Listener` (the walker recurses and fires enter/exit callbacks).

code

typescript · 14 lines
typescript
// Base visitor: default = full child walk. Concrete passes override selectively.
abstract class BaseVisitor implements Visitor<void> {
  visitAddition(a: Addition) { a.left.accept(this); a.right.accept(this) }
  visitNumber(_: NumberLiteral) { /* leaf */ }
}

// Pass that prunes: never descends into a function body it doesn't care about.
class CollectTopLevelNames extends BaseVisitor {
  names: string[] = []
  visitFunctionDecl(f: FunctionDecl) {
    this.names.push(f.name)
    // deliberately NOT calling super -> subtree skipped
  }
}

go deeper

for a junior

Note that something must walk the tree and that the simplest version is accept recursing into children.

for a middle

Compare the three owners with concrete pros and cons, and mention the base-visitor-with-default-walk idiom.

for a senior

Tie the choice to concrete needs — pruning, early exit, return-value composition, enter/exit scoping — and cite ANTLR Visitor vs Listener or a compiler pass framework.

for a principal

Cover cycles/DAG memoization, stack depth and worklist conversion, rewriting via new-tree transformers, and parallel traversal with pure visitors and result merging.

### Why traversal is a separate concern at all The Visitor pattern says nothing about *how* you reach each element — GoF explicitly lists the object structure (or an iterator, or the visitor) as candidates. That silence causes real design debate, because the choice determines what visitors can and cannot do. ### Option 1 — element-driven traversal (`accept` recurses) ``` class Addition { accept(v) { v.visitAddition(this); left.accept(v); right.accept(v) } } ``` **Pros** - Client code is one call: `root.accept(v)`. - Every visitor gets full coverage for free; no visitor can forget to recurse (a common and nasty bug). - Traversal logic written once per element type. **Cons** - The order is baked into the element classes. Want post-order for one pass and pre-order for another? You can't, without adding flags or a second accept variant. - No **pruning**: a visitor that only cares about function declarations still walks every expression in every body. - No **early exit**: a "does this tree contain X?" visitor must walk the whole tree (or throw an exception as control flow — a well-known smell). - No natural place for **enter/exit** pairs, which passes need for scoping (push a symbol-table scope on the way in, pop on the way out). - Poor fit for **return values**: combining children's results (`visit(Addition) = visit(left) + visit(right)`) requires the parent to control the recursion. ### Option 2 — visitor-driven traversal (`accept` is one line; `visit` recurses) ``` class Addition { accept(v) { return v.visitAddition(this) } } class Evaluate implements Visitor<int> { visitAddition(a) { return a.left.accept(this) + a.right.accept(this) } } ``` **Pros** - Full control: pre-order, post-order, in-order, or none; skip subtrees; stop early by returning; track depth or path in visitor fields. - Natural composition of return values — enables pure, stateless, recursive visitors. - Contextual state (current scope, current class, error accumulator) is threaded naturally. **Cons** - Every visitor repeats the walk, and **forgetting to recurse silently produces wrong results** — the single most common Visitor bug in practice. - Mitigation, and the standard industry answer: an abstract `BaseVisitor` (ANTLR's `AbstractParseTreeVisitor`, `javax.lang.model.util.SimpleElementVisitor`, Roslyn's `CSharpSyntaxWalker`) whose default `visit` methods perform the complete child walk. Concrete visitors override only the node kinds they care about and call `super.visitX(node)` to continue. This gives you option 1's safety with option 2's control, and it is what most real systems ship. ### Option 3 — external walker / iterator A `TreeWalker` object owns the traversal and calls `node.accept(v)` (or fires callbacks) per node. **Pros** - Order is a swappable strategy: DFS, BFS, reverse post-order, worklist, or parallel walking, chosen independently of both hierarchies. - One walk implementation reused by all visitors, no per-visitor duplication. - Enables listener-style **enter/exit** callbacks around each node — ANTLR's `ParseTreeWalker` + `Listener` is exactly this. **Cons** - The walker must know how to get children, which means elements expose their structure (`children()`), further eroding encapsulation. - Control-flow-shaped operations become awkward: a listener cannot easily skip a subtree or return a value, because it is not driving the recursion. ANTLR documents exactly this — use `Listener` for straightforward, order-independent work and `Visitor` when you need return values or to control which children get visited. ### Choosing | Need | Choose | |---|---| | Simple, uniform, always-full walk | Element-driven, or a walker with listeners | | Return values composed from children | Visitor-driven | | Skip subtrees / early exit | Visitor-driven | | Enter/exit scope pairs | Walker+listener, or visitor-driven with explicit push/pop | | Multiple traversal orders over the same structure | External walker (order as a strategy) | | Cyclic or shared (DAG) structures | Whoever drives must carry a visited-set; visitor-driven or walker, never naive element recursion | ### Edge cases worth naming - **Cycles and DAGs.** Naive recursion loops forever or does exponential duplicate work. Keep an identity-based visited set in the driver. In a DAG, decide explicitly whether shared subgraphs are visited once (memoized) or once per path. - **Depth.** Deep trees blow the stack with recursive walks; an explicit worklist/stack in an external walker is the standard fix (Roslyn, for instance, avoids deep recursion in parts of its syntax walking for this reason). - **Mutation during traversal.** Rewriting passes usually build a *new* tree (a transformer/rewriter visitor returning nodes) rather than mutating in place, precisely to avoid iterator-invalidation-style hazards. - **Thread safety.** A visitor holding accumulation state is not safe to share across a parallel walk; either make visitors pure with return values, or give each worker its own visitor and merge results.

  • What is the most common bug in visitor-driven traversal, and how do you prevent it?
    Forgetting to recurse into children in an overridden visit method, so part of the tree is silently skipped. Prevent it with an abstract base visitor whose defaults perform the full walk, so overriding without calling super is a visible, deliberate choice — and test with a coverage-counting visitor.
  • When would you prefer ANTLR's Listener over its Visitor?
    When the pass is a straightforward full walk with no return values and no need to skip subtrees — the ParseTreeWalker drives, you just implement enter/exit callbacks. Use Visitor when you need to compute and combine results or control which children are visited.
  • How do you visit a graph with cycles?
    Keep an identity-based visited set (or mark bits) in whatever drives the traversal, check on entry, and decide explicitly whether shared nodes in a DAG are visited once (memoized) or once per path — the two give different results for things like size or cost computations.

A guided tour of a building. Either the building's signage forces one fixed route (element-driven), each guide chooses their own route and can skip floors (visitor-driven), or a shuttle driver runs a fixed circuit while guides just talk at each stop (external walker + listener).

saying these in an interview costs you the question

  • Assuming the Visitor pattern dictates the traversal order — it doesn't specify traversal at all
  • Overriding a visit method and forgetting to recurse, then blaming the pattern for 'losing' nodes
  • Using exceptions as early-exit control flow instead of letting the visitor drive recursion
  • Ignoring cycles/DAGs and getting infinite loops or exponential re-visits
  • Sharing one stateful visitor across a parallel walk

context

resolving links…