Skip to content

BFS Level Order

A Different Way to Walk

Every traversal so far — preorder, inorder, postorder, recursive or iterative — has been depth-first. You pick a direction and go as deep as possible before backtracking. DFS explores by depth of exploration.

BFS does the opposite. It processes all nodes at distance 1 from the root, then all nodes at distance 2, then distance 3, and so on. It explores by distance from the root.

DFS explores by depth of exploration. BFS explores by distance from root. When the problem cares about levels, layers, or distance — reach for BFS.

The data structure swap tells the whole story: replace the stack (LIFO) with a queue (FIFO), and DFS becomes BFS.

BFS processing nodes level by level using a queue, compared to DFS going depth-first with a stack

The Tree

         1          ← level 0
       /   \
      2     3       ← level 1
     / \   / \
    4   5 6   7     ← level 2

Basic Level-Order Traversal

The template: push the root into a queue. While the queue isn't empty, record its current size (that's how many nodes are on this level), then dequeue exactly that many nodes. For each, process it and enqueue its children.

vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> levels;
    if (!root) return levels;
    queue<Node*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        vector<int> currentLevel;
        for (int i = 0; i < levelSize; i++) {
            Node* current = nodeQueue.front();
            nodeQueue.pop();
            currentLevel.push_back(current->value);
            if (current->left) nodeQueue.push(current->left);
            if (current->right) nodeQueue.push(current->right);
        }
        levels.push_back(currentLevel);
    }
    return levels;
}

Level-Order Trace

Step Queue (front→back) levelSize Dequeue & Process Enqueue Children
Init [1] — — —
Level 0 [1] 1 1 2, 3
Level 1 [2, 3] 2 2 → enqueue 4,5; then 3 → enqueue 6,7 4, 5, 6, 7
Level 2 [4, 5, 6, 7] 4 4, 5, 6, 7 (all leaves, no children) —

Result: [[1], [2, 3], [4, 5, 6, 7]]

The critical trick is levelSize = nodeQueue.size() captured before the inner loop. As you dequeue nodes and enqueue their children, the queue grows — but you only process the original levelSize nodes for this level. The children wait for the next iteration of the outer loop.

When BFS vs DFS

Problem Type Use Why
"Level by level" anything BFS You naturally get level boundaries
Shortest path in unweighted graph/tree BFS First time BFS reaches a node = shortest distance
Zigzag, right view, max width BFS These are all level-aware problems
Path sum, diameter, LCA DFS These need root-to-leaf paths or bottom-up aggregation
Serialize/deserialize Either BFS gives level-order; DFS gives preorder

The rule of thumb: if the problem mentions "level," "depth," "layer," "distance from root," or "width" — start with BFS.

Zigzag Traversal

Problem: Return the level-order traversal but alternate the direction at each level. Level 0: left to right. Level 1: right to left. Level 2: left to right. And so on.

The standard BFS template already gives you one level at a time. The only twist: on odd-numbered levels, reverse the current level's vector before adding it to the result.

vector<vector<int>> zigzagTraversal(Node* root) {
    vector<vector<int>> levels;
    if (!root) return levels;
    queue<Node*> nodeQueue;
    nodeQueue.push(root);
    bool leftToRight = true;
    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        vector<int> currentLevel(levelSize);
        for (int i = 0; i < levelSize; i++) {
            Node* current = nodeQueue.front();
            nodeQueue.pop();
            int insertIndex = leftToRight ? i : (levelSize - 1 - i);
            currentLevel[insertIndex] = current->value;
            if (current->left) nodeQueue.push(current->left);
            if (current->right) nodeQueue.push(current->right);
        }
        levels.push_back(currentLevel);
        leftToRight = !leftToRight;
    }
    return levels;
}

Instead of reversing, we place each value at the correct index directly. When leftToRight is true, index \(i\) maps to position \(i\). When false, index \(i\) maps to position \(\text{levelSize} - 1 - i\).

Zigzag Trace

Level leftToRight Queue Before Nodes Dequeued insertIndex Mapping Level Result
0 true [1] 1 0→0 [1]
1 false [2, 3] 2, 3 0→1, 1→0 [3, 2]
2 true [4, 5, 6, 7] 4, 5, 6, 7 0→0, 1→1, 2→2, 3→3 [4, 5, 6, 7]

Result: [[1], [3, 2], [4, 5, 6, 7]]

Verify: Level 0 left-to-right: [1]. Level 1 right-to-left: [3, 2]. Level 2 left-to-right: [4, 5, 6, 7]. Correct.

Right Side View

Problem: Imagine standing to the right of the tree and looking left. Return the values of the nodes you can see — one per level, always the rightmost.

         1    ← you see 1
       /   \
      2     3    ← you see 3
     / \   / \
    4   5 6   7    ← you see 7

Answer: [1, 3, 7].

This is BFS where you only care about the last node on each level.

vector<int> rightSideView(Node* root) {
    vector<int> result;
    if (!root) return result;
    queue<Node*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        for (int i = 0; i < levelSize; i++) {
            Node* current = nodeQueue.front();
            nodeQueue.pop();
            if (i == levelSize - 1) {
                result.push_back(current->value);
            }
            if (current->left) nodeQueue.push(current->left);
            if (current->right) nodeQueue.push(current->right);
        }
    }
    return result;
}

Right Side View Trace

Level levelSize Nodes Processed Last Node (i == levelSize-1) Result
0 1 1 1 (i=0, levelSize-1=0) [1]
1 2 2, 3 3 (i=1, levelSize-1=1) [1, 3]
2 4 4, 5, 6, 7 7 (i=3, levelSize-1=3) [1, 3, 7]

Result: [1, 3, 7]

Right side view, left side view, bottom view, top view — these are all BFS with a filter on which node to keep at each level.

Maximum Width of Binary Tree

Problem: Find the maximum width among all levels. Width of a level is the number of positions between the leftmost and rightmost non-null nodes (inclusive), counting null nodes in between.

Consider this tree:

         1
       /   \
      2     3
     /       \
    4         7

Level 0: width 1 (just node 1). Level 1: width 2 (nodes 2 and 3). Level 2: width 4 (positions 4, , , 7 — four positions from leftmost to rightmost).

The trick: assign each node a position index. If a node is at position \(p\), its left child is at \(2p\) and its right child is at \(2p + 1\). This is the same indexing as a heap array.

Width of a level = (rightmost position) - (leftmost position) + 1.

int maxWidth(Node* root) {
    if (!root) return 0;
    int maximumWidth = 0;
    queue<pair<Node*, unsigned long long>> nodeQueue;
    nodeQueue.push({root, 0});
    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        unsigned long long leftmostPosition = nodeQueue.front().second;
        unsigned long long rightmostPosition = leftmostPosition;
        for (int i = 0; i < levelSize; i++) {
            auto [current, position] = nodeQueue.front();
            nodeQueue.pop();
            rightmostPosition = position;
            unsigned long long normalizedPosition = position - leftmostPosition;
            if (current->left) {
                nodeQueue.push({current->left, 2 * normalizedPosition});
            }
            if (current->right) {
                nodeQueue.push({current->right, 2 * normalizedPosition + 1});
            }
        }
        unsigned long long currentWidth = rightmostPosition - leftmostPosition + 1;
        maximumWidth = max(maximumWidth, (int)currentWidth);
    }
    return maximumWidth;
}

We normalize positions by subtracting leftmostPosition at each level to prevent integer overflow. The children's positions are computed from the normalized parent position.

Width Trace (on the tree above)

Level Nodes (value, pos) leftmost rightmost Width
0 (1, 0) 0 0 1
1 (2, 0), (3, 1) 0 1 2
2 (4, 0), (7, 3) 0 3 4

Maximum width: 4

BFS Complexity

For any tree with \(n\) nodes:

  • Time: \(O(n)\) — every node is enqueued and dequeued exactly once.
  • Space: \(O(w)\) where \(w\) is the maximum width of the tree. In the worst case (a complete binary tree), the last level has \(\lceil n/2 \rceil\) nodes, so space is \(O(n)\).

Compare with DFS space: \(O(h)\) where \(h\) is the height. For a balanced tree, \(h = O(\log n)\) which is much less than \(w = O(n)\). For a skewed tree, \(h = O(n)\) and \(w = O(1)\).

BFS uses more memory than DFS on wide trees (balanced). DFS uses more memory than BFS on deep trees (skewed). Pick based on the tree shape you expect.

Try It

The starter code has a zigzagTraversal function with a TODO. Fill it in and verify:

Level 0 (L→R): 1
Level 1 (R→L): 3 2
Level 2 (L→R): 4 5 6 7

Predict before running: What's the maximum queue size during BFS on our 7-node complete binary tree? At level 2, all 4 nodes are in the queue simultaneously. So the max queue size is 4.

Challenge: Modify level-order traversal to return levels in bottom-up order: [[4,5,6,7], [2,3], [1]]. You don't need to change the BFS — just reverse the result at the end.

Challenge 2: Solve right side view using DFS instead of BFS. (Hint: do a preorder traversal that goes right before left. The first node you see at each depth is the rightmost.)

Edge Cases to Watch For

  • Maximum width overflow: For wide, deep trees, position indices in the heap-style numbering (\(2p\), \(2p+1\)) can overflow int or even long long. Always normalize positions by subtracting the leftmost position at each level.
  • Zigzag index calculation with levelSize = 1: When a level has a single node, the formula levelSize - 1 - i yields 0, which is correct. But verify this boundary doesn't cause off-by-one errors in your implementation.

Problems

Problem Link Difficulty
LC 102 — Binary Tree Level Order Traversal leetcode.com/problems/binary-tree-level-order-traversal Medium
LC 103 — Binary Tree Zigzag Level Order Traversal leetcode.com/problems/binary-tree-zigzag-level-order-traversal Medium
LC 199 — Binary Tree Right Side View leetcode.com/problems/binary-tree-right-side-view Medium
LC 662 — Maximum Width of Binary Tree leetcode.com/problems/maximum-width-of-binary-tree Medium
LC 107 — Binary Tree Level Order Traversal II leetcode.com/problems/binary-tree-level-order-traversal-ii Medium