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.

Answer 1

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