Breadth-first tree search

The tree search version of breadth-first search explores action histories in nondecreasing length without automatically removing repeated states. A finite branching factor ensures that every finite depth contains finitely many histories, so the method is a complete search algorithm for goals reachable at finite depth. With equal positive action costs it is an optimal search algorithm for total action cost. It need not terminate on an unsolvable instance with an infinite search tree, and it need not optimize a terminal reward unrelated to depth.

Maintain a FIFO queue of child iterators ordered by the breadth-first order of their parents. Consume a child from the front iterator and append a deferred iterator for that child's children; discard empty front iterators as needed. This enumerates descendants without first materializing a whole child list or level. On a locally finite tree, each node occurs after finitely many earlier outputs. If an earlier level is infinite, strict breadth-first order cannot put a deeper node at any finite output position; that obstruction is inherent in the requested ordering.