There is another type of modified tree traversal which is often found useful. It is called a branch and bound traversal. An algorithm for this traversal is as follows:
Nonrecursive Branch and Bound Traversal
1. Set p to t.
2. Set bag to empty.
3. While p is not null
if p is feasible, then
i. process(t,p), and
ii. add each successor pointer of p to the bag;
Select a pointer from the bag and set p to it.
This algorithm uses a data abstraction consisting of a bag data structure and operations on the bag that set it to empty, test it for emptiness, select (and remove) a pointer from it, and add a pointer to it. The idea is to define the select operation so that it removes the pointer from the bag that points to the node most likely to lead to a solution. The execution time required by the branch and bound traversal is directly related to how well the select function does the job of picking the next node to process and how well the feasible function does its job of pruning the tree. The better the selection and pruning the better the execution time. The select function should return null if the bag is empty.
If the select function always selects the node most recently added to the bag, then the data abstraction becomes a stack, and the algorithm is turned into a backtracking depth-first traversal. If the select function always selects the node that was added earliest to the bag, then the data abstraction becomes a queue, and the algorithm is turned into a backtracking breadth-first traversal. Thus backtracking may be viewed as a special case of branch and bound.
Horowitz and Sakni [1978] contains extensive discussions of backtracking and branch and bound traversals, with many applications worked out in detail. Also see Golomb and Baumert [1965]. Wirth [1976] deals with these techniques for problem solving; in particular, the stable marriage problem and the eight-queens problems are solved recursively.