Tracking depth in a non-recursive breadth first search

breadth-first-search, language-agnostic, tree

Solution

Just store the depth with the nodes and increment it every time you generate a node's children.

q := [(root, 0)]
while q:
    n, depth := q.pop()
    yield n, depth
    if n has children:
        c := children of n
        for i in c:
            q.append(i, depth + 1)

This idea extends to DFS and heuristic-guided search.

Problem

I have the following algorithm for a breadth first search: ``` q := [] q.append(root node of tree) while q: n := q.pop(0) yield n if n has children: c := children of node for i in c: q.append(i) ``` 1) How could this be extended so it keeps track of the current depth? 2) Would this extension apply to a similar algorithm for depth first search, with the queue `q` replaced by a stack?

Original source