Uses a recursively called simple generator (with the same arguments as the outer call!) to traverse a tree in breadth first order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
def breadth_first(tree,children=iter): """Traverse the nodes of a tree in breadth-first order. The first argument should be the tree root; children should be a function taking as argument a tree node and returning an iterator of the node's children. """ yield tree last = tree for node in breadth_first(tree,children): for child in children(node): yield child last = child if last == node: return
This is an example of the self-recursive generators discussed in http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/221457
A little care is needed (the lines containing variable "last") to avoid getting into an infinite recursion for trees that are not themselves infinite. The recursive call is always traversing one level higher than the outer call, so if the two calls ever reach a situation where both have the same most-recently-output node, we must have traversed the whole tree. If the tree has height h, nodes at distance d from the root are traversed by h-d instances of the generator. When the number of nodes grows by at least a constant factor in each level (e.g. complete binary trees) it takes only constant time per tree node on average. Unlike the usual queue-based BFS, the space used is only O(h).