Skip to main content

Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips

Geraint Jones and Jeremy Gibbons

Abstract

This paper is about an application of the mathematics of the zip, reduce (fold) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first tree traversal algorithm, and of a subtle and efficient breadth-first tree labelling algorithm.

Institution
Dept of Computer Science‚ University of Auckland
Month
may
Note
Also IFIP Working Group 2.1 working paper 705 WIN−2
Number
7No.1
Year
1993