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.
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
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.
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