Breadth First Search (BFS)

About

Is a Graph or Tree traversal algorithm used to explore nodes and edges. It can also be used as a Search algorithm.

It is widely used in numerous situations such as shortest-path calculations, network analysis, and more.

It doesn't preserve shape of the traversal.

It uses Queue to store nodes in order.

Each node is visited once, and all its edges are traversed once.

For a Graph with V vertices and E edges, $O(V+E)$.

For a Tree with N nodes, $O(N)$.

How it works

BFS explores all nodes at the current "depth" (or level) before moving to nodes at the next depth.

In more Detail

In Graphs, you must also mark visited nodes, so that they don't get pushed again to the Queue.

In BST where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the needle value.

1. At start node N:

   1. Push N to the Queue.

   2. Push N's children to the Queue.

   3. Process N and remove it from the Queue.

2. Go to next node N at Queue:

   1. Push its children to the Queue.

   2. Process node N, and remove it from Queue.

3. Repeat 2. until all nodes were processed.

// Considering a Binary Tree
function bfs(head: BinaryNode<T>, needle: T): boolean {
    // Using a TS ArrayList will make it run in O(n²), because of shift/unshift of ArrayLists
    const queue = [head];
    
    while (queue.length) {
        const node = queue.shift();
        // Needle found
        if (node.value === needle) return true;
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return false;
}