Hybrid recursive graph search in javascript

Graph search. It comes up all the time in programming interviews. Can you write a program to search a graph? Can you do it depth first? Can you do it breadth first? Can those be done recursively?

I like this line of questions because it hits on a few fundamental data structures and programming concepts. We hit on stacks vs. queues and we hit on the difference between imperative and recursive programming approaches.

In a depth first search we work with a stack. If written imperatively, that stack is managed by the programmer. If written recursively, that stack is managed by the programming language. In a breadth first search the mechanics are pretty much the same but we work with a queue instead.

There is an interesting point in this line of questions when the interviewer asks “Can you write a breadth first search recursively?”. The interviewer has brought the candidate through the introductory paces of transforming loops into recursive functions and back again. They’ve covered the basic data structures and are now looking to see if the candidate understands their use. The general answer to this question is that you can not write a breadth first search recursively. Why? Recursion leverages a call stack. When a recursive function calls itself a new frame is pushed onto the stack. When the function returns, that frame is popped off of the stack. This implicit stack management is what recursive depth first search relies on. Breadth first search leverages a queue instead of a stack. We can’t recurse in breadth first search because we need a queue and the programming language would give us a stack. Instead we must manage the queue by hand.

OK great, so why is this an interesting juncture in the interview? Well, I’m a javascript developer. There are strange bits around the language but they yield some cool behaviors. I found myself wondering if there was a way to get a queue for free via recursion in the same way that we can get a stack for free in all other languages. It turns out that there is a way and it has to do with the javascript engine, execution environment, and the event loop.

So what are these things? The javascript engine is the rig that compiles your javascript code down to machine code on the fly. There are a variety of engines out there but the most notable ones are Google’s V8, Microsoft’s Chakra, Mozilla’s SipderMonkey, and Apple’s JavaScriptCore. All of these engines run inside of some other execution environment such as a browser or Node.js. The javascript engine and the environment in which it executes can communicate to each other, but not directly. When the engine wants to get the execution environment to do something (V8 making an ask of Chrome for example) it must use an API to do so. When the environment wants to get the engine to due something it puts that request into a queue for the engine to work on when it has time. This is where the event loop comes into play. For a more in depth description of the event loop check out Phillip Roberts’ excellent talk on the subject. The gist of it is that the event loop is in charge of managing the queue of things the execution environment has lined up for the javascript engine to do. When the engine has nothing left in its call stack, the event loop looks for things in the queue, pops them off of the queue, and pushes them onto the engine’s stack.

Let’s make that a little bit more concrete. One of the things that javascript folks used to do a bunch of is call computations in a setTimeout with a delay of zero milliseconds. They would do this to prioritize render and layout logic over their computations and ensure smooth UIs. setTimeout is a browser API that tells the browser to execute a callback after some number of milliseconds. When called with a zero millisecond delay the callback is handed over to the execution environment and immediately put into the queue. The callback is then picked up by the event loop if and when the javascript engine has an empty stack. This was such a common use case for UI animation that browser vendors created the requestAnimationFrame API which is an optimized version of the immediately returned setTimeout use case.

Now back to the interview. With our excursion into javascript’s internals behind us we can start to think about how we can get our queue in a recursive function. So we’re on the same page, we’ll work on a tree search problem with nodes that are defined as follows

and build a tree to search

We can build a straight forward depth first search function that will recursively call itself and log each node’s id attribute just before it returns

Running our depth first search on the root node prints out 6, 4, 2, 5, 3, 1. Great, we are running down the left side of the tree and then down the right side of the tree. Our Depth first search is doing exactly what we would expect given that we are letting the javascript engine manage these recursive calls in its stack. What does this look like if we don’t allow the engine to manage these calls in it’s stack? Instead what happens if we try to make the stack feel like a queue by throwing these calls out of the engine and into the execution context. The idea is that we can bully the stack into feeling like a queue by only ever letting one of these calls in at a time. The rest of the calls will pile up and wait their turn in the queue. Once the stack is empty, the event loop will politely place another call in the stack. We can do this by defining a a breadth first search function that looks like our depth first search function but abuses an API to get the calls out of the engine and managed by the queue and event loop

Alright, running this guy on root prints out 1, 2, 3, 4, 5, 6. The number order has changed which means so has our search strategy. Very cool. What that means is we can express search both ways in a really concise recursive definition by sprinkling in some sweet JS know how.

Is there anything more interesting we can do with this? You bet! As the title implies, we can perform a hybrid search that operates as a depth first or breadth first search depending on some internal logic. We now have the power to choose our search strategy on the fly depending on the properties of the node we are looking at. For example we might want to use breadth first search on the left nodes in our tree and a depth first search on the right nodes.

Running this one on root, we see that it prints out 5, 3, 1, 2, 4, 6. The right nodes (odd numbers) come back to us first in a depth first fashion followed by the left nodes (even numbers) in a breadth first fashion. What is going on here? The right nodes are pushed onto the stack and get printed out as they come off the stack. Meanwhile, the left nodes have been kicked out the javascript engine and into the execution environment. Once the engine’s stack clears the event loop starts pulling nodes out of the queue and into the engine’s stack. Once in the stack the node is printed out.

Pretty cool, but also pretty contrived. What about doing something a little bit more practical? How about finding the lowest valued pixel in an image? When walking over the pixels of an image, you could start with a pretty poor guess of the best pixel in the image and improve your guess from there. If we start with our poor guess and walk all of its neighbors recursively until we’ve touched all of the pixels we will eventually find the lowest valued pixel. We can do better than that though. Armed with our hybrid search we can add some heuristics. In most real world images, objects are contiguous sets of pixels. When we get on the gold of a dark spot, we are going to want to go deep on the pixels in that spot. To do this we can keep track of the darkest pixel we’ve seen. With that stashed away we can go deep on pixels that are darker and wide on those that are lighter. In most cases, we’ll find the lowest valued pixel faster

The best algorithm ever written? Not by a long shot. I like it though because it makes use of some pretty interesting javascript stuff to get a job done in an unexpected way.

Show your support

Clapping shows how much you appreciated Corey Flynn’s story.