Tagged: tail recursion

Trees and continuation passing style

For no reason in particular I decided to revisit tree traversal as a kind of programming kata. There are two main kinds of tree traversal:

  • Depth first – This is where you go all the way down a tree’s branches first before bubbling up to do work. With a tree like below, you’d hit c before doing any work since it’s the deepest part of the tree (assuming you iterated left first then right) 
         a
    / \
   b   e
 /  \
c    d
  • Breadth first – This is where you hit all the nodes at the level you’re on before going further. So with the same tree, you’d hit a, then b, then e, then c and d.

Being as I actually hate tree traversal, and having to think about it, I decided that whatever I write better be extensible and clean.

Depth first

Here is a simple DFS … Read more

The largest mass problem

I was recently asked to write some code to find the largest contiguous group of synonymous elements in a two dimensional array. The idea is that you want to find the largest “land mass” in a problem where you have a game board that looks something like

L L L W
W L L W
L W W W
W L L W

Where L stands for land, and W stands for water. In this example, the largest land mass would be of size 5. But there are also 2 other land masses, one of size one, and another of size two. Elements can be contiguous only if their direct adjacent neighbor is the same type, so diagonals don’t count.

In general, you can think of the largest mass problem as almost exactly the same as the flood fill problem in image graphics. Except with flood fill, you are given … Read more