Performing Breadth First Search recursively

Question

Let's say you wanted to implement a breadth-first search of a binary tree recursively. How would you go about it?

Is it possible using only the call-stack as auxiliary storage?

Answer 1

I can implement recursively but using extra storage. I can mimic the iterative approach. Have function signature as bfs(queue q). The first call will have q=[root]

bfs(queue<siblings> q):
  iterate over the entire queue;
  form the newqueue q which has all the children of nodes in q;
  call bfs(q);

Answer 2

I couldn't find a way to do it completely recursive (without any auxiliary data-structure). But if the queue Q is passed by reference, then you can have the following silly tail recursive function:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

Answer 3

If you use an array to back the binary tree, you can determine the next node algebraically. if i is a node, then its children can be found at 2i + 1 (for the left node) and 2i + 2 (for the right node). A node's next neighbor is given by i + 1, unless i is a power of 2

Here's pseudocode for a very naive implementation of breadth first search on an array backed binary search tree. This assumes a fixed size array and therefore a fixed depth tree. It will look at parentless nodes, and could create an unmanageably large stack.

bintree-bfs(bintree, elt, i)
    if (i == LENGTH)
          return false

    else if (bintree[i] == elt)
          return true

    else 
        bintree-bfs(bintree, elt, i+1)        

Answer 4

The dumb way:

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}

Answer 5

(I'm assuming that this is just some kind of thought exercise, or even a trick homework/interview question, but I suppose I could imagine some bizarre scenario where you're not allowed any heap space for some reason [some really bad custom memory manager? some bizarre runtime/OS issues?] while you still have access to the stack...)

Breadth-first traversal traditionally uses a queue, not a stack. The nature of a queue and a stack are pretty much opposite, so trying to use the call stack (which is a stack, hence the name) as the auxiliary storage (a queue) is pretty much doomed to failure, unless you're doing something stupidly ridiculous with the call stack that you shouldn't be.

On the same token, the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm. This makes it no longer breadth first search on a binary tree, and thus the run-time and whatnot for traditional BFS no longer completely apply. Of course, you can always trivially turn any loop into a recursive call, but that's not any sort of meaningful recursion.

However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.