CodeWithYash

Intermediate · Module 13 · Lesson 3

Level-order BFS

Process tree nodes one depth at a time.

15–25 min readLesson 72 of 123

Lesson 72 of 123

1d streak

Breadth-First Search (BFS): Level-Order Traversal

Level-Order Traversal visits nodes depth by depth: first level 0 (root), then all nodes at level 1, then all nodes at level 2. Because it explores horizontally, it is implemented with a Queue (FIFO).

Queue Snapshot State Machine per Level
Tree:
         [ 3 ]          Level 0
        /     \
     [ 9 ]   [ 20 ]     Level 1
             /    \
          [ 15 ]  [ 7 ]  Level 2

Queue Trace:
Level 0: Queue = [ 3 ]. Size = 1.
         Process 3 -> Output: [3]. Children added: 9, 20.
Level 1: Queue = [ 9, 20 ]. Size = 2.
         Process 9  -> Children: none.
         Process 20 -> Children added: 15, 7.
         Output: [9, 20].
Level 2: Queue = [ 15, 7 ]. Size = 2.
         Process 15, 7.
         Output: [15, 7].

Final Levels: [[3], [9, 20], [15, 7]]
LevelOrderBfs.java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // Lock level snapshot size
        List<Integer> currentLevel = new ArrayList<>(levelSize);

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}

The levelSize Snapshot Invariant

Recording int levelSize = queue.size(); before entering the inner loop is mandatory. As children are enqueued inside the loop, queue.size() grows dynamically. Freezing levelSize ensures the loop processes exactly the nodes belonging to the current depth level.

Cost Model

Complexity & Trade-offs

Graph processing
O(n)
O(w)
Assumes adjacency-list representation unless stated otherwise.

When to use it

  • Hierarchies, ordered sets/maps, expression trees, and recursive aggregation.
  • Path, ancestor, depth, and subtree questions.
  • Maintaining sorted dynamic data with balanced trees.

Common mistakes

  • Assuming a BST is balanced without a balancing guarantee.
  • Confusing node depth with subtree height.
  • Discarding information needed by the parent instead of returning it.

Practice prompts

  • Reproduce the worked Level-order BFS example without looking at the trace.
  • Change one input condition and explain whether the Level-order BFS invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.