Depth-first search visits a node, follows its descendants, and only then moves to another branch at the same level. A tree traversal visits each node once. Unlike breadth-first traversal, it finishes the deeper part of a branch before visiting its siblings. section 8.4
Visit timing matters. In pre-order traversal, a function runs on a parent before descending, so a transformation can change the path that follows. In post-order traversal, it runs after the children, allowing their results to be combined at the parent. section 8.4 section 8.4.2
Turn a nested vector into a sequence
In `(tree-seq vector? identity [1 [2 3] 4])`, `vector?` identifies branches and `identity` supplies their children. The lazy result visits the root, then each branch before its contents: `([1 [2 3] 4] 1 [2 3] 2 3 4)`. The result can be consumed without traversing the entire tree. section 9.3.2
Choose the traversal interface to match the job:
- `tree-seq` returns a lazy sequence of nodes; supply a branch predicate, a children function, and a root. section 9.3.2
- `clojure.walk/prewalk` and `postwalk` transform nested data. Use pre-order to act before descending or post-order to process completed branches, as when evaluating an expression tree. section 8.4.2
- `file-seq` lazily descends into a directory as soon as it encounters it. It uses `tree-seq` for filesystem traversal. section 9.3.3
- A `clojure.zip` zipper separates navigation from processing. `zip/next` offers depth-first movement, but locations also permit a different or partial traversal. section 8.4.4
For a quick ordering check, `prewalk-demo` visits `[1 [2 [3]] 4]` before `1`, while `postwalk-demo` visits `1`, `2`, and `3` before reporting their enclosing vectors. The distinction is about when a node is processed, not whether its branch is explored. section 8.4.1
