Breadth-First Search

Tags

Breadth-First Search

Category

Graphs

Difficulty

Medium

Problem Statement

Given a graph represented as a tree of nodes where each node has a name and a list of children, implement a breadth-first search method that traverses the graph and returns an array of all node names in BFS order (level by level, left to right).

Intuition

Breadth-first search explores all nodes at the current depth level before moving to nodes at the next depth level. A queue naturally models this: we process the front node, then enqueue all its children. Since a queue is FIFO, children are processed in the order they were added, and all nodes at depth d are processed before any node at depth d+1.

Approach

  1. Initialize a queue with the root node.
  2. Initialize an empty results array.
  3. While the queue is not empty:
    • Dequeue the front node.
    • Add its name to the results array.
    • Enqueue all of its children (in order).
  4. Return the results array.

Pseudocode

class Node:
    name
    children

    function breadthFirstSearch(results):
        queue = [self]
        while queue is not empty:
            current = queue.dequeue()
            results.append(current.name)
            for child in current.children:
                queue.enqueue(child)
        return results

Time & Space Complexity

  • Time: O(v + e) where v is the number of vertices and e is the number of edges. Each node and edge is processed once.
  • Space: O(v) — the queue can hold up to an entire level of nodes. In the worst case (a very wide tree), this could be close to v. The results array also stores v names.

Key Insights

  • BFS guarantees level-order traversal, which DFS does not.
  • BFS finds the shortest path (in terms of number of edges) from the source to any node in an unweighted graph.
  • The queue is the defining data structure for BFS, just as the stack is for DFS.
  • For trees, no "visited" tracking is needed. For general graphs with cycles, a visited set must be maintained.

Edge Cases

  • Single node with no children: return an array with just that node's name.
  • Very wide tree (e.g., a node with thousands of children): the queue may hold many nodes simultaneously.
  • Null/empty root: return an empty array.
  • All nodes are in a single chain (like a linked list): BFS and DFS produce the same order, and the queue never holds more than one node at a time.

Linked mentions