Breadth-First Numbering : Okasaki's Beautiful Algorithm

Over the weekend I was grokking functional data structures and bumped into a functional pearl by Chris Okasaki from the publications of ICFP 2000. The paper is titled Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design - it indeed unfolds a beautiful algorithm and explains in detail the philosophy and thought process that went into designing it the unconventional way that he did. The part which intrigued me most was that this ingenuous (and yet simple) design did seem to him a mostly straightforward answer, while almost all other functional programmers to whom he presented the problem over the next year, did come up with a baroque solution approach, in a completely different direction than his own. Okasaki calls this the communal blind spot, that was steering programmers away from what seemed to be a very natural solution.

The Problem

Quoting it straight from the paper ..

Given a tree T, create a new tree of the same shape, but with the values at the nodes replaced by the numbers 1 .. |T| in breadth first order

For example, given the following tree ..

breadth-first numbering should yield the tree ..

Solve It !

Traditional solution approach would be one based on an explicit level based traversal of the tree that makes multiple passes over each level computing the length, collecting the children and finally rebuilding the level. Nothing wrong with the approach .. only slightly baroque .. and uses the plain old lists as the data structure for processing the tree. So, nothing to be excited about, no aha! moments and nothing instrinsically beautiful to write about.

Okasaki's approach was based on the fact that there already exists a breadth-first search algorithm based on functional queues, that allows O(1) queue operations. Hence using the queue as the sequencing ADT allows constant time addition and removal of trees from the front and back of the queue. He simply extended it to compute the breadth-first numbering. And he started with a more generalized version of the problem of computing the breadth-first numbering for a forest and using it to solve the same for a single tree.

It actually took me very little time to implement the functional algorithm in Scala. In fact it took much more time to implement the traditional level based traversal algorithm, since it involved complex list manipulations. Once again a lesson that proper choice of data structures always lead to more elegant solutions.

Here is the Scala implementation ..

trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]

def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
  if (trees.isEmpty) Queue.Empty
  else {
    trees.dequeue match {
      case (E, ts) =>
        bfsNumForest(i, ts).enqueue[Tree[Int]](E)
      case (Node(d, l, r), ts) =>
        val q = ts.enqueue(l, r)
        val qq = bfsNumForest(i+1, q)
        val (bb, qqq) = qq.dequeue
        val (aa, tss) = qqq.dequeue
        tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
    }
  }
}

def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
  val q = Queue.Empty.enqueue[Tree[T]](t)
  val qq = bfsNumForest(1, q)
  qq.dequeue._1
}


The beauty of the algorithm is that the implementation looks exactly the same as the specification, so long you are implementing in a functional language. In a recent blog post, Okasaki has also come up with a visual representation of this algorithm. Take it side by side with the implementation .. and you have the "quality without a name" feeling.