Tree BFS

Level-order traversal via a queue. Right-side view, zigzag, per-level aggregation, connecting next-right pointers, and shortest path in unweighted trees.

13 problems 3 Easy 5 Medium 5 Hard

Level-order traversal via a queue. Each iteration processes one full level; the queue size at the start of the loop is the level's width — record it before processing or you'll lose track. Useful for level-aware aggregations, right-side view, zigzag, and connecting next-right pointers in O(1) auxiliary space when the tree has parent links.

When to reach for this pattern

Process nodes level by level
Right-side view, level averages, level sums
Shortest path / distance in a tree or implicit tree (word ladder)
Populate next-right pointers

Canonical template

queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
    int sz = q.size();           // freeze level size BEFORE processing
    for (int i = 0; i < sz; ++i) {
        TreeNode* n = q.front(); q.pop();
        // process; emit per-level info
        if (n->left) q.push(n->left);
        if (n->right) q.push(n->right);
    }
    // end of level
}

C++ · adapt the names and types to your problem.

Common pitfalls

Recording level size mid-loop instead of at entry — the queue has grown by then
Null-root edge case: every iteration breaks if the queue starts with a null
Zigzag: reverse on alternating levels, not on every level
Memory: BFS holds an entire level at once — wide trees can blow up the queue

Related patterns

Tree DFS Graphs

Tree BFS

When to reach for this pattern

Canonical template

Common pitfalls

Related patterns

Problems (13)

Keyboard shortcuts