Introduction

Breadth-first traversal is easy to describe and easy to implement imperatively with a mutable queue. In Clojure, the functional version works best when you keep the same core idea but use an immutable queue, typically clojure.lang.PersistentQueue, instead of trying to force the problem into naive recursion over lists.

Why a Queue Is the Key Abstraction

Depth-first traversal fits plain recursion naturally because the next node to visit is always "the next child." Breadth-first traversal is different. You must remember the remaining siblings and cousins while you walk the current level.

That is a queue problem:

• take the next node from the front
• append its children to the back
• repeat until the queue is empty

Trying to write BFS without an explicit queue often leads to awkward concat chains and less clear code.

A Simple Tree Representation

We will represent a tree node as a map with a :value and a :children vector:

1(def tree
2  {:value 1
3   :children [{:value 2
4               :children [{:value 5 :children []}
5                          {:value 6 :children []}]}
6              {:value 3 :children []}
7              {:value 4
8               :children [{:value 7 :children []}]}]})

The expected breadth-first order is:

[1 2 3 4 5 6 7]

Idiomatic Functional BFS with loop and recur

In Clojure, loop and recur are still functional. They do not mutate state in place; they create efficient tail-recursive iteration with new bindings at each step.

1(defn bfs-values [root]
2  (loop [queue (conj clojure.lang.PersistentQueue/EMPTY root)
3         result []]
4    (if (empty? queue)
5      result
6      (let [node (peek queue)
7            rest-queue (pop queue)
8            next-queue (reduce conj rest-queue (:children node))]
9        (recur next-queue (conj result (:value node)))))))
10
11(bfs-values tree)
12;; => [1 2 3 4 5 6 7]

This is usually the cleanest answer:

• 'peek reads the front of the queue'
• 'pop removes the front'
• 'reduce conj appends children to the back'

Nothing is mutated, but the algorithm still has the right shape for BFS.

Why concat Is Often the Wrong Tool

A first attempt at functional BFS often looks like:

(concat (rest queue) (:children node))

That can work at a toy level, but it changes the data structure into a lazy sequence rather than preserving queue semantics explicitly. The code becomes less direct about what is happening, and performance characteristics become less obvious.

With PersistentQueue, the queue behavior is stated in the code instead of being simulated indirectly through list operations.

Returning Nodes Instead of Values

Sometimes you want the nodes themselves rather than just their :value fields. The traversal can be adjusted easily:

1(defn bfs-nodes [root]
2  (loop [queue (conj clojure.lang.PersistentQueue/EMPTY root)
3         result []]
4    (if (empty? queue)
5      result
6      (let [node (peek queue)
7            rest-queue (pop queue)
8            next-queue (reduce conj rest-queue (:children node))]
9        (recur next-queue (conj result node))))))

That keeps the traversal logic identical and only changes what gets accumulated.

A Lazy Version

If you want a lazy breadth-first sequence, you can wrap the same idea in lazy-seq:

1(defn bfs-seq [queue]
2  (lazy-seq
3    (when-not (empty? queue)
4      (let [node (peek queue)
5            rest-queue (pop queue)
6            next-queue (reduce conj rest-queue (:children node))]
7        (cons (:value node) (bfs-seq next-queue))))))
8
9(defn breadth-first [root]
10  (bfs-seq (conj clojure.lang.PersistentQueue/EMPTY root)))
11
12(take 4 (breadth-first tree))
13;; => (1 2 3 4)

This is useful when the consumer may not need the whole traversal immediately.

Why This Is Still Functional

Some developers worry that using loop means the solution is no longer functional. In Clojure, that is the wrong distinction. The key questions are:

• are you mutating shared state
• are your values immutable
• is the function referentially transparent

The queue in the example is immutable. Each step produces a new queue binding. That is still functional programming, just expressed in an efficient idiomatic form rather than as deeply nested recursion.

Common Pitfalls

The most common mistake is trying to write BFS with plain recursive descent over children and accidentally implementing depth-first traversal instead.

Another issue is using list operations such as concat without being clear about queue behavior. The code may work, but the intent becomes murkier and the cost model harder to reason about.

Developers also sometimes assume loop and recur are somehow unfunctional. In Clojure, they are standard tools for immutable iterative processes.

Finally, make sure every node has a :children collection, even if it is empty. If some nodes omit the key or use nil, your traversal should normalize that case or the reduce step may behave inconsistently.

Summary

• Functional BFS in Clojure is easiest when you model the algorithm explicitly with an immutable queue.
• 'clojure.lang.PersistentQueue/EMPTY is the standard queue starting point.'
• 'loop and recur are idiomatic and still functional in Clojure.'
• Prefer queue operations such as peek, pop, and conj over improvised concat chains.
• A lazy breadth-first sequence is possible once the queue-based version is clear.