#Walking Subtrees

The walker is an in-memory traversal helper. You hand it a loaded subtree, you get a generator that yields nodes in DFS pre-order, DFS post-order, or BFS — plus a visitor-form walk() that exposes depth, parent, and sibling info per visit.

It is purely a consumer of data you have already loaded. The walker never queries the database.

#1. What you get

// Pre-order DFS — root first, then each subtree left-to-right.
foreach ($electronics->dfs() as $node) {
    echo $node->name, "\n";
}

// Visitor form with per-visit context.
$electronics->walk(function (Model $node, WalkContext $ctx) {
    echo str_repeat('  ', $ctx->depth), $node->name, "\n";
});

// One-liner for "give me the subtree as a Collection in pre-order".
$ordered = $electronics->flattenedSubtree();

Five public methods land on every NodeTrait model:

#2. The loaded-subtree contract

When you omit $subtree, the walker reads $this->descendants. If the relation is not loaded and you pass no collection, it throws UnloadedSubtreeException:

$electronics->walk($visitor);
// UnloadedSubtreeException: the walker is in-memory only — call
// ->load('descendants') first or pass a collection explicitly
// ($subtree argument). The walker does not query the database.

Three load patterns cover almost every case:

// 1. Eager-load up front (one query).
$root = Category::with('descendants')->find($id);
$root->walk($visitor);

// 2. Lazy-load on demand (one extra query).
$root = Category::find($id);
$root->load('descendants');
$root->walk($visitor);

// 3. Explicit, scoped load — the walker honours whatever slice you supply.
$slice = $root->descendants()->where('depth', '<=', 2)->get();
$root->walk($visitor, subtree: $slice);

The explicit form is the right tool when you want to walk a partial subtree — the walker treats nodes whose children are missing from the slice as leaves and keeps going.

#3. Strategies side by side

For the tree

Electronics
  Laptops
  Phones
    iPhone
    Android

each strategy yields a different order:

(The pre-order and BFS orders happen to match on this shallow tree because every parent has its children grouped under it. On deeper trees they diverge.) The lft / rgt badges on each row give you the underlying nested-set bounds the walker uses internally — DFS pre-order is the same order as iterating by lft ascending, which is why an already-loaded descendants relation walks for free.

Pre-order is the default everywhere — it's what humans expect, and what every other tree-printing utility in this package uses.

#4. The visitor signature

walk() calls your closure as

function (Model $node, WalkContext $ctx): WalkSignal|null

WalkContext carries everything the walker knows about the current visit:

The absolute depth column on the node is unchanged — read it via $node->getDepth() if you need it.

The ASCII-tree branch-character problem is the canonical motivating example:

$electronics->walk(function (Model $node, WalkContext $ctx) {
    $branch = match (true) {
        $ctx->depth === 0      => '',
        $ctx->isLastSibling     => '└── ',
        default                 => '├── ',
    };
    echo $branch, $node->name, "\n";
});

#5. Signals

Return a WalkSignal from the visitor to steer the walk:

$electronics->walk(function (Model $node, WalkContext $ctx) {
    if ($node->name === 'Phones') {
        return WalkSignal::SkipSubtree;
    }
    if ($node->discontinued) {
        return WalkSignal::Stop;
    }
});

#6. Pruning with WalkFilter

WalkFilter is the static-pruning counterpart to the visitor's runtime signals. Use it when the decision about whether to visit a node doesn't depend on what the visitor does — depth ceilings, predicates, "skip everything trashed" rules.

use Vusys\NestedSet\Walker\WalkFilter;

// Root + two levels.
$electronics->walk($visitor, filter: WalkFilter::depth(2));

// Only nodes the predicate accepts. Pruned nodes' subtrees are
// also skipped — there is no way to skip one node but visit its
// children.
$electronics->walk($visitor, filter: WalkFilter::where(
    fn (Model $n, WalkContext $ctx) => $n->active,
));

// AND two filters together: stricter depth wins; predicates compose.
$filter = WalkFilter::compose(
    WalkFilter::depth(3),
    WalkFilter::where(fn (Model $n, WalkContext $ctx) => $n->published),
);

// The instance-form `andThen()` reads better in pipelines.
$filter = WalkFilter::depth(3)->andThen(WalkFilter::where($predicate));

The full shape of a filter:

Every walker method — dfs(), dfsPostOrder(), bfs(), walk(), flattenedSubtree() — accepts a WalkFilter as its last argument.

#7. Generators vs walk()

dfs(), dfsPostOrder(), bfs() return PHP generators. walk() takes a callback. Both shapes are useful:

// Generator — break early.
foreach ($electronics->dfs() as $node) {
    if ($node->matches($query)) {
        return $node;
    }
}

// Visitor — context-rich rendering.
$lines = [];
$electronics->walk(function (Model $n, WalkContext $ctx) use (&$lines) {
    $lines[] = str_repeat('  ', $ctx->depth) . $n->name;
});

The generators do not support WalkSignal::SkipSubtree — they iterate every node the filter admits and let you break or continue externally. If you need dynamic per-node descent control, use walk().

#8. flattenedSubtree()

A convenience for "give me an ordered Collection" — composition of walk() + collect:

$ordered = $electronics->flattenedSubtree('pre');
$ordered = $electronics->flattenedSubtree('bfs', filter: WalkFilter::depth(2));

The difference between flattenedSubtree('pre') and descendants()->defaultOrder()->get() is where the work happens:

• flattenedSubtree reads the already-loaded collection and reorders in PHP. No SQL.
• defaultOrder()->get() issues a fresh ORDER BY lft query against the database.

If you have already loaded the subtree, flattenedSubtree is free. If you haven't, do the query.

#9. Pitfalls

Other rough edges to know about:

#9.1 Orphans

Nodes in the loaded collection whose parent_id doesn't match any other loaded row (and isn't the walk root) are unreachable from the root and silently skipped. Walk by reachability, not by raw membership.

#9.2 Partial loads are honoured

If you load only depth 0 + 1, the walker treats the depth-1 nodes as leaves. It will not fetch their children for you.

#9.3 Attribute mutations are fine

Mutating non-structural attributes (e.g. $node->name = 'new') inside a visitor is safe — the walker doesn't observe attribute changes. The structural index is only sensitive to parent_id.

#10. Comparison with toTree()

NodeCollection::toTree() (see In-memory Tree Shaping) and the walker share the same input shape (a flat collection) but answer different questions.

Choose the walker when you only need to visit each node. Choose toTree() when you need the nested arrays to hand to a template.

#11. UnloadedSubtreeException

Thrown by walk() / dfs() / dfsPostOrder() / bfs() / flattenedSubtree() when no explicit $subtree is supplied and the descendants relation is not loaded. Resolution: eager-load with ->load('descendants') or pass a collection explicitly. The walker never issues its own queries — this exception forces the load decision to be visible at the call site so a deliberately narrowed subtree is never accidentally widened.