= Solution
Keep a <FIFO queue> of pending child <iterators>, ordered by the breadth-first order of their parents. Defer even the call creating a node's children until that <iterator> reaches the front and is needed:
``
def breadthFirst[T](node: Node[T]): Iter[Node[T]] = {
def childrenLater(n: Node[T]): Iter[Node[T]] = new Iter[Node[T]] {
private lazy val children = n.children()
def hasNext: Boolean = children.hasNext
def next(): Node[T] = {
require(children.hasNext, "empty child iterator")
children.next()
}
}
val pending = scala.collection.mutable.Queue.empty[Iter[Node[T]]]
pending.enqueue(childrenLater(node))
new Iter[Node[T]] {
private def normalize(): Unit = {
while (pending.nonEmpty && !pending.head.hasNext) pending.dequeue()
}
def hasNext: Boolean = {
normalize()
pending.nonEmpty
}
def next(): Node[T] = {
normalize()
require(pending.nonEmpty, "no more descendants")
val answer = pending.head.next()
pending.enqueue(childrenLater(answer))
answer
}
}
}
``
Here \b[“descendants” excludes the supplied root]: the first output is its first child. A self-inclusive convention can prepend `unitIter(node)` without changing the traversal logic. The queue invariant says its <iterators> enumerate the still-unreported children of already encountered parents, in parent breadth-first order. Consuming one child appends that child's deferred <iterator> after all earlier parents' pending children. Exhausted child <iterators> contribute nothing and can be discarded. This proves increasing depth and sibling order without constructing a complete level in advance.
This <lazy breadth-first traversal with child iterators> never eagerly materializes all children or the whole tree. A finite prefix can therefore be traversed on a genuinely infinite tree. As with any strict breadth-first ordering, an infinite earlier level prevents reaching a deeper level; no algorithm can place a deeper node after every member of an infinite earlier level at a finite output position. For a <locally finite tree>, every finite-depth level is finite and each descendant is eventually reached, assuming the underlying <iterator> operations terminate. Fresh child <iterators> and exclusive ownership of consumed <iterator> states are essential to this argument.
Back to article page
