Look, Ma, no queues!

A very classic, if a bit overrated exercise, is to print a tree in width-first order. Also called level-order, it means you print your binary tree row-by-row, with the nodes of depth d, leftmost first, before the nodes of depth d+1.

This is sort of a fizzbuzz for recurison and basic data structure usage, because while there are many ways to cheat in this problem, the standard and expected solution involves a queue. In Scala:

abstract class Tree
case class Node(value: Int, left: Tree, right:Tree) extends Tree
case class Leaf(value:Int) extends Tree


def printLevelsWithQueue(t:Tree): List[Int] = {
  val q = Queue[Tree](t)
  def print_aux(q: Queue[Tree]): List[Int] =
    if (q.isEmpty) Nil else {
      val (tree, remq) = q.dequeue
      tree match{
        case Leaf(v) => v :: print_aux(remq)
        case Node(v, l, r) => v :: print_aux(remq :+ l :+ r)
      }
    }
  print_aux(q)
}

Now, the interesting thing is that this needs not be : you can write this function without a single queue, by simply writing an auxiliary function that returns the lines the printout of the tree should be a part of, each of them a List[Int]. So, the end result is a list of lines, a List[List[Int]].

 def printLevelsWithNoQueueAndMultipleRecursion(t:Tree): List[Int] = {
   def print_aux_rec(t:Tree): List[List[Int]] = t match {
     case Leaf(v) => List(List(v))
     case Node(v, l, r) => {
       val leftLines = print_aux_rec(l)
       val rightLines = print_aux_rec(r)
       List(v) :: ((leftLines,rightLines).zipped map {(l1,l2) => l1:::l2})
     }
   }
   print_aux_rec(t).flatten
 }

Sadly, this function is horrendously costly, with multiple recursive calls, and a number of list appends that doubles for each level of the tree: one for the second level from the root, two for the third level, etc.

Now, dealing with the append problem would involve passing list buffers around for the lines, instead of lists — which isn’t particularly interesting in and of itself. But I thought it would be nice to get rid of the multiple recursion. That’s a simple continuation-passing style translation:

def printLevelsWithNoQueuesAndCPS(t:Tree): List[Int] = {

  def print_aux_rec_cps(t:Tree, andThen: List[List[Int]] => List[List[Int]]): List[List[Int]] = t match {
    case Leaf(v) => andThen(List(List(v)))
    case Node(v, l, r) => {
      def newThen = (leftLines:List[List[Int]]) =>
       print_aux_rec_cps(r, (rightLines: List[List[Int]]) =>
       andThen (List(v) :: ((leftLines, rightLines).zipped map (_ ::: _))))
      print_aux_rec_cps(l,newThen)
    }
  }
  print_aux_rec_cps(t,{(x) => x}).flatten
}

Now, the problem with writing that in Scala is that the tail call optimization done in the compiler is relatively simple, and doesn’t deal with the imbricated recursive call here, even though this is a clear tail recursive function. And incidentally, that’s not so much of a problem : somebody writing a CPS-translated, list buffer-passing function in anything but a playful context is clearly out of his mind.

But if you want to play with that function, seeing if it makes the stack explode, you may want to generate big trees. How would we do that ?

Well, one of the ways to do that is to help yourself with one of the ways to cheat with the initial question of printing a tree in level order: the cheat is to represent the tree as a table, where the $k$-th node of the $d$-th level has index $2^{d-1}+k-1$. Using this correspondence, we can write a recursive function to generate that big tree of depth $n$:

def bigExample(n: Int, k: Int):Tree =
  if (n == 0) Leaf(k) else {
    import scala.math._
    val left = bigExample(n-1, k+1)
    val right = bigExample(n-1, k + pow(2,n).toInt)
    Node(k, left, right)
  }

Oh, but wait ! This is again multiply recursive and hard on the stack ! CPS translation to the rescue:

def bigExample_cps(n:Int, k:Int, andThen:Tree => Tree): Tree =
  if (n == 0) andThen(Leaf(k)) else {
    import scala.math._
    def nextThen = (l:Tree) =>
      bigExample_cps(n-1, k+pow(2,n).toInt,
                     (r:Tree) => andThen(Node(k,l,r)))
    bigExample_cps(n-1,k+1,nextThen)
  }

Sadly, we are faced again with the limitations of the Scala TCO, which indicates we might want to generate that tree using some other way to put the data on the stack. It would suffice to generate the tree bottom-up, instead of top-down, writing something that would look like, for example, the combination function of a certain Huffman coding exercise (that’s a personal message to followers of Martin Odersky’s course on functional programming).

Or, we could try with a language that has a better optimization. I have a full gist of Ocaml code for you to play with. There you’ll also find all the code in this post.