Dovetailing (computer science)

Dovetailing is a technique in Algorithm design (such an algorithm is sometimes referred to as a dovetailer). It refers to performing a search in a Tree data structure in a breadth-first search, rather than depth-first search manner. This preference is useful when the tree potentially contains a path of infinite length - if a depth-first search was used, part of the tree would potentially never be explored. Accordingly a breadth-first search is used, which visits nodes according to their distance from the root. This avoids the problem caused by a depth-first search moving down an infinite path.

This technique is known as dovetailing in analogy with the interleaving ends of a dovetail joint in woodworking.