= Solution
Use the heap-numbered binary tree with root label zero and children $2k+1,2k+2$. Its strict descendants in <breadth-first search> order are \b[$1,2,3,\ldots$]. A machine-safe `Node[Int]` version stops at the largest representable label:
``
class NumberNode(val label: Int) extends Node[Int] {
require(label >= 0)
def children(): Iter[Node[Int]] = new Iter[Node[Int]] {
private var candidate = 2L * label.toLong + 1L
private val last = candidate + 1L
def hasNext: Boolean = candidate <= last && candidate <= Int.MaxValue
def next(): Node[Int] = {
require(hasNext)
val answer = new NumberNode(candidate.toInt)
candidate += 1L
answer
}
}
}
val traversal = breadthFirst(new NumberNode(0))
var expected = 1
while (expected <= 1000) {
assert(traversal.hasNext)
assert(traversal.next().label == expected)
expected += 1
}
``
The arithmetic is widened before computing child labels, so no negative wrapped labels occur. Repeated `hasNext` calls should not skip nodes; a leaf root should produce immediate exhaustion, and uneven finite trees should retain sibling order across parents. A fresh second traversal should start again at one.
Literal unbounded increase is impossible with the bounded `Int` type. For a genuinely infinite test, change the label and child arithmetic to `BigInt`; the same construction then has no representational endpoint. The shown finite-prefix test already exercises lazy traversal without allocating the entire very large `Int`-labelled tree.
Back to article page
