Understanding BFS with Queue Visualization

BFS Queue Visualization

Let's look at how BFS traverses a tree using a queue:

Tree Structure

     A
   /   \
  B     C    // B and C are children of A
 / \   / \   // D,E are children of B
D   E F   G  // F,G are children of C

• Each node has exactly one parent
• Relationships are one-way (down only)
• B is a child of A, but A is not a child of B

Here's how we'd implement BFS for a tree in TypeScript:

// Tree node structure
class TreeNode {
  value: string;
  children: TreeNode[];

  constructor(value: string) {
    this.value = value;
    this.children = [];
  }
}

// BFS implementation for tree
function treeBFS(root: TreeNode): string[] {
  const result: string[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    // Get the next node from the front of the queue
    const node = queue.shift()!;
    result.push(node.value);

    // Add all children to the queue
    for (const child of node.children) {
      queue.push(child);
    }
  }

  return result;
}

// Example usage
const treeA = new TreeNode('A');
const treeB = new TreeNode('B');
const treeC = new TreeNode('C');
const treeD = new TreeNode('D');
const treeE = new TreeNode('E');
const treeF = new TreeNode('F');
const treeG = new TreeNode('G');

treeA.children = [treeB, treeC];
treeB.children = [treeD, treeE];
treeC.children = [treeF, treeG];

console.log(treeBFS(treeA)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G']

Let's see how BFS traverses this tree using a queue (starting from A):

1. Initial state:

Queue: [A]

2. Process A, enqueue its children (B, C):

Queue: [B, C]
Level 1 complete

3. Process B, enqueue its children (D, E):

Queue: [C, D, E]

4. Process C, enqueue its children (F, G):

Queue: [D, E, F, G]
Level 2 complete

5. Process remaining nodes (D, E, F, G):

Queue: [E, F, G] → [F, G] → [G] → []
Level 3 complete

Final traversal order: A → B → C → D → E → F → G

Notice how:

1. We process all nodes at the same level before moving deeper
2. The queue ensures we visit nodes in order of their distance from root A
3. Each node is processed exactly once
4. We don't need to track visited nodes because trees don't have cycles
5. The queue naturally maintains the level-order traversal