BFS in JavaScript using Recursion

Question

It is easy to do DFS using recursion:

function dfs(tree, fn, level) {
  fn(tree, level)
  tree.children.forEach(function(child){
    dfs(child, fn, level + 1)
  })
}

However every example I have seen of BFS uses a queue and is iterative rather than recursive. Wondering if there is any way to define a recursive BFS algorithm.

Similar to https://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively ? If your graph is a tree, you can use iterative deepening. If it is a general graph, you'll have to pay the memory cost, but you can pass the queue on the stack to make it 'recursive'. — Thomas Ahle, Jun 22 '18 at 11:10
Yeah similar to that but there wasn't a clear answer, unless the answer is no you can't do it. (couldn't tell if that's what they were saying). I would like to see what it would take to do it recursive. — Lance, Jun 22 '18 at 11:13
You can always write the loop as a (tail-)recursive function, but you cannot do away with the queue. It's inherent in BFS. — Bergi, Jun 22 '18 at 11:50

score 2 · Accepted Answer · edited May 19 '23 at 15:00

If sibling nodes can be ordered and have information or a way to retrieve information about their siblings, we can execute in the order of a breadth first search. Clearly, with abstract data, building the tree as we go, like calculating a subsequent chess move, this may be impossible or prohibitively complicated. Tree data structures, however, could be built with provisions for sibling information.

Here's an example with dummy 'sibling' and 'done' functions. If we're not guaranteed each node has children, we may want an extra parameter to record the last seen child. Note that 'next sibling' could be akin to a linked list but could also be implemented as a method of calculating what the next sibling is based on known information.

function bfs(tree, fn) {
  fn(tree);
  
  if (tree.done) return;
  
  if (tree.isLastSibling)
    bfs(tree.children.firstSibling(), fn);
  else
    bfs(tree.nextSibling(), fn);
}

var c4 = {
  val: 'c4',
  isLastSibling: true,
  done: true
}

var c3 = {
  val: 'c3',
  nextSibling: () => c4
}

var c2 = {
  val: 'c2',
  nextSibling: () => c3
}

var c1 = {
  val: 'c1',
  nextSibling: () => c2
}

var b2 = {
  val: 'b2',
  isLastSibling: true,
  children: {firstSibling: () => c1}
}

var b1 = {
  val: 'b1',
  nextSibling: () => b2
}

var a = {
  val: 'a',
  isLastSibling: true,
  children: {firstSibling: () => b1}
}

bfs(a, tree => console.log(tree.val))

Yay this is exactly what I was looking for! Thank you :) – Lance Jun 22 '18 at 19:51 — Lance, Jun 22 '18 at 19:51

BFS in JavaScript using Recursion

1 Answers1