7.6.4 Breadth-first

One final point about the backtracking traversal algorithm. Suppose the while loop task is replaced by the task:

if p is not null, then

if p is feasible, then

process(p)

push all successors of node.p onto the stack

pop(sp)

else

pop(s,p).

This implementation also represents a preorder tree traversal. The stack is used to store and recall postponed obligations. It can be further modified by changing the stack to a queue and replacing empty, push, and pop by the corresponding queue operations. Pop must return null if called when the queue is empty. The result is another modified general tree traversal, a backtracking breadth-first traversal. It accesses the nodes in level order. In contrast, the backtracking preorder traversal presented earlier might be called a backtracking depth-first traversal. Removing the "p is feasible" test of the backtracking breadth-first traversal turns it into a breadth-first traversal. You should convince yourself that this version leads to the nodes of Figure 7.13(a) being accessed and processed in the order A, B, C, D, E, F, G, H, I, J, K, L, M. Keep in mind that in this application the root node was never considered. The difference between a backtracking traversal and a traversal is that backtracking tests for feasibility. This allows tree paths to be ignored when it can be determined that they cannot lead to a solution.