Binary Tree Level Order Traversal (BFS Level by Level)

• Tree BFS pattern – visit nodes level by level using a FIFO queue.
• Level-size snapshot – at the start of each level, record queue.size() to know how many nodes belong to this level.
• Drain and enqueue – dequeue exactly that many nodes, collect their values, and enqueue their non-null children.
• Result – a list of lists, each inner list holding one level's values left to right.
• Complexity – O(n) time, O(w) space where w is the maximum width of the tree.

What is Level Order Traversal?

Level order traversal visits all nodes on one level before moving to the next level. It goes from top to bottom, and within each level from left to right. The result is a list of lists, where each inner list contains the values of one level.

This is the Tree Breadth First Search (BFS) pattern, and it is the foundation for many tree BFS variants.

How does the level-size snapshot work?

The essential trick is capturing levelSize = queue.size() at the start of each level. This snapshot tells you exactly how many nodes belong to the current level. You drain precisely that many nodes, enqueuing each node's children. Everything enqueued during that drain belongs to the next level.

package com.bank.service;

import java.util.*;

public class HierarchyLevelPrinter {

    static class TreeNode {
        int approvalAmount;
        TreeNode left, right;
        TreeNode(int val) { this.approvalAmount = val; }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

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

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

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.approvalAmount);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1000);
        root.left = new TreeNode(500);
        root.right = new TreeNode(800);
        root.left.left = new TreeNode(200);
        root.left.right = new TreeNode(300);
        root.right.right = new TreeNode(400);

        System.out.println("Level order: " + levelOrder(root));
    }
}

Level order: [[1000], [500, 800], [200, 300, 400]]

What variants does the Tree BFS pattern support?

The level-size snapshot is the reusable core that every Tree BFS variant builds on.

| Variant | Modification |
|---|---|
| Reverse level order | Add each level at the front of the result list |
| Zigzag level order | Flip direction flag per level |
| Right side view | Take only the last node of each level |
| Left side view | Take only the first node of each level |
| Level averages | Compute the average of each level |
| Minimum depth | Return depth at first leaf encountered |
| Maximum depth | Count total levels processed |
| Connect siblings | Wire next pointers within each level |

// Reverse level order: add level at front
result.add(0, level); // instead of result.add(level)

// Right side view: take last element
if (i == levelSize - 1) rightView.add(node.approvalAmount);

How is BFS different from DFS for trees?

| Aspect | BFS (Level Order) | DFS (In/Pre/Post) |
|---|---|---|
| Data structure | Queue | Stack (or recursion) |
| Visit order | Level by level | Deep before wide |
| Space | O(width) | O(height) |
| Best for | Level grouping, shortest path | Sorted output, path problems |
| Balanced tree space | O(n/2) at bottom level | O(log n) |
| Degenerate tree space | O(1) single-width | O(n) full depth |

For a balanced tree, BFS uses more memory because the bottom level holds about n/2 nodes. For a deep narrow tree, BFS uses less. The choice depends on the tree shape and the problem.

// DFS uses O(height) stack space
public static void dfs(TreeNode node) {
    if (node == null) return;
    System.out.println(node.approvalAmount);
    dfs(node.left);
    dfs(node.right);
}
// Space: O(log n) balanced, O(n) degenerate

What are the edge cases?

• Null root – return empty list.
• Single node – return [[root.val]].
• Left-skewed tree – each level has one node; result has n inner lists of size 1.
• Perfect binary tree – bottom level has n/2 nodes, which is the peak queue size.

// Edge case: null root
System.out.println(levelOrder(null)); // []

// Edge case: single node
TreeNode single = new TreeNode(42);
System.out.println(levelOrder(single)); // [[42]]

What are common mistakes?

The most common mistake is forgetting to snapshot the level size, causing the inner loop to process nodes from multiple levels.

// WRONG: no level-size snapshot
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    // This processes one node at a time, losing level boundaries
}

// CORRECT: snapshot level size
while (!queue.isEmpty()) {
    int levelSize = queue.size(); // snapshot before draining
    for (int i = 0; i < levelSize; i++) {
        TreeNode node = queue.poll();
        // process
    }
}

What is the time and space complexity?

Time is O(n) because every node is enqueued and dequeued exactly once. Space is O(w) for the queue, where w is the maximum width. For a balanced tree, w is about n/2 at the bottom level. The result list uses O(n) for all values.

What should a senior engineer know?

A senior engineer should know that the level-size snapshot is the universal building block for all Tree BFS problems. Every variant (zigzag, right view, connect siblings, min/max depth) uses the same queue loop with the same snapshot. The modification is always in how each dequeued node's value is used, not in the traversal itself.

They should also understand the space trade-off with DFS: for wide trees BFS uses more memory, for deep trees DFS uses more. In production systems with very wide trees (like B-trees), BFS queues can become large, and iterative deepening DFS can be a memory-efficient alternative.