Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design (Functional Pearl)

✨ Summary

Summary

Chris Okasaki examines the problem of replacing the labels in a binary tree with consecutive integers assigned in breadth-first order while preserving the tree’s shape. The paper develops the solution by first generalizing breadth-first traversal from trees to forests, then representing the pending forest with a queue. For numbering, the algorithm threads both the current index and the partially constructed output through the forest. Because input forests are consumed from the front while output forests are produced in reverse order, ordinary functional queues can be used for both roles. Assuming constant-time queue operations, the resulting algorithm runs in linear time and uses a standard purely functional queue representation.

The paper contrasts this queue-based design with a level-oriented list-based algorithm. The level-oriented method explicitly processes one level at a time and performs multiple passes over each level; it is somewhat easier to derive using lists, but neither approach is presented as categorically superior. Okasaki argues that programmers’ strong preference for level-oriented solutions may result from premature commitment to lists, programming-language features such as pattern matching, and insufficient use of abstract data types. Views are presented as a way to retain pattern-matching-like definitions while using abstract queue representations.

The appendix discusses the lazy circular breadth-first-numbering technique associated with Jones and Gibbons. In that approach, the list of starting indices for each level is tied recursively to the algorithm’s output; laziness permits this feedback loop. The paper’s principal contribution is therefore both algorithmic and methodological: it demonstrates a linear-time strict functional solution and uses the exercise to illustrate how abstraction and delayed commitment to concrete data structures can change algorithm design.

Documented influence

A later paper on strictifying circular programs uses Okasaki’s breadth-first-numbering example as an extended case study. It derives non-circular and strict implementations from the lazy circular formulation and reports performance comparisons among the resulting variants, directly extending the paper’s discussion of strict versus lazy functional implementations. (researchgate.net)

The algorithm has also been reused as an example in later functional-programming work on breadth-first applicative traversals: a 2021 paper presents a breadth-first traversal combinator and uses it to define breadth-first tree renumbering. (doisinkidney.com) Okasaki later published an explanatory visual presentation of the algorithm, indicating continued use as a teaching and exposition example. (okasaki.blogspot.com)