Algorithm for "balanced" breadth-first search

Question

I'm looking for references for an algorithm that conducts a breadth-first tree search in a balanced manner that is resilient in a situation where

• we expect most nodes to have few children, but
• a few nodes may have a many (possibly infinitely many) children.

Consider this simple tree (modified from this post):

     A
   /   \
  B     C
 /     /  \
D     E    F
|    /|\    \
G   HIJ...   K

Depth-first visits nodes in this order:

A B D G C E H I J ... F K

Breadth-first visits nodes in this order:

A B C D E F G H I J ... K

The balanced breadth-first algorithm that I have in mind would visit nodes in this order:

A B C D E G F H K I J ...

Note how

• we visit G before F, and
• we visit K after H but before I.

G is deeper than F, but it is an only child of B whereas F is a second child of C and must share its search priority with E. Similarly between K and the many children H, I, J, ... of E.

I call this "balanced" because a node with lots of children cannot choke the algorithm. Concretely, if E has 𝜔 (infinitely) many nodes then a pure breadth-first strategy would never reach K, whereas the "balanced" algorithm would still reach K after H but before the other children of E.

_{(The reader who does not like 𝜔 can attain a similar effect with a large but still finite number such as "the greatest number of steps any practical search algorithm will ever make, plus 1".)}

I can only imagine that this style of search or something like it must have been the subject of much research and practical application. I would be grateful to be pointed in the right direction. Thank you.

Answer 1

Transform your tree to a different kind of representation. In this new representation, each node has at most two links: one to its leftmost child, and one to its right sibling.

     A
   /   \
  B     C
 /     /  \
D     E    F
|    /|\    \
G   HIJ...   K

  ⇓

     A
   /  
  B --> C
 /     /  
D     E -> F
|    /      \
G   /        K
   /
  H -> I -> J -> ...

Then treat this representation as a normal binary tree, and traverse it breadth-first. It may have an infinite height, but like with any binary tree, the width at any particular level is finite.