Recursive Breadth-first Traversal

One of my coworkers [1] brought to my attention an interesting problem. What’s the best way to run a breadth-first traversal on a tree data structure using recursion?  He already had an initial algorithm working correctly, but it had some unfortunate characteristics that made it less than ideal.  I haven’t dealt directly with the plethora of tree algorithms that are out there for several years, so I mentioned the few things I could remember off the top of my head and we talked about the problem for a few minutes.  In the end we decided that a better algorithm was probably possible, but we weren’t sure exactly what it would look like.

However, that wasn’t the end of it (if it was this would be a boring blog post).  Afterwards the problem was still bugging me so I made some internet searches.  The general consensus from my initial search was that breadth-first traversal should be done with an iterative algorithm using a queue data structure.  A recursive approach is possible, but you would basically be converting the iterative solution into a tail-call recursive solution where adding to the queue and looping would instead be accomplished by adding to the queue and making a recursive call.  This recursive solution works, but it didn’t feel different enough to me to decide that there was any real reason to use it over the iterative solution.  I thought about it for a while [2] and came up with this solution:

type 'a tree = 
    | Node of ('a tree) list * 'a 
                                  
let ($) f a = f a 
let listFlatten l =     
    match l with         
        | [] -> []
        | _ -> List.reduce (List.append) l
         
let map f (Node(_, item)) = f item 
let breadthFirstTraversal visit t =
     let gatherChildren (Node(children,_)) = children
     let derivative f = (fun (Node (children,_)) -> listFlatten $ List.map f children)
     let rec helper tree selectNodes =
         let children = selectNodes tree in
             match children with
                 | [] -> ()
                 | _ -> ((for child in children do map visit child); helper tree (derivative selectNodes))
                   
     in map visit t
      ; helper t gatherChildren

This solution is recursive with respect to the node selector.  I realized that you can “take the derivative” of a function that selects children nodes.  The first derivative would select grand-children nodes, the second would select great-grand-children nodes, etc.  In this code snippet, the first couple of definitions are just a tree type definition and some helper functions.  All of the real work occurs in the “breadthFirstTraversal” function.  The “gatherChildren” function is the initial node selector function.  The “derivative” function modifies it so that it returns the next level of children.  And finally, the recursive calls happen in the “helper” function.  Each time a recursive call is made we take the derivative of the node selector in order to get the next level of the tree.

Now, while this is an interesting take on the breadth-first traversal problem (one that is really only possible with higher order functions), I’m not sure that this is the best route to take for handling breadth-first searches in production code.  However, I do think this this code represents an aspect of software engineering that is both a challenge and an opportunity.  There are many problems that we solve with software where the best solution is not always obvious and sometimes surprising alternatives exist right under the surface, waiting to be discovered.  The challenge is in searching for the solution that best fits the need at hand, but the opportunity is that our next interesting unanswered question may hold exciting new benefits.

[1] – Trevon Sutton is one of our accomplished Software Engineers who deserves special thanks for coming up with the initial recursive algorithm and insisting that there ought to be a better way to achieve the desired goal.

[2] – Actually, my first solution turned out to be a confusingly implemented depth-first traversal.  The solution after that turned out to have the same problem that Trevon’s initial solution had.

You Might Also Like

• Monadic Complexity Resolutions
• The Future is Optional
• Lambda Calculus