Pattern 16 of 27

Tree BFS and Level Order

Process a tree one level at a time with a queue when the answer depends on depth or on nodes that sit side by side.

Cost: O(n) time, O(w) space, where w is the widest level
Problems: 6

When to reach for it

The prompt says level, row, depth order, or right side view.
You need the shallowest node that meets some condition.
Nodes on the same level have to be linked or compared.

How it works

A queue visits nodes in the order they were discovered, which for a tree means level by level. What turns plain BFS into level-order traversal is reading the queue length before processing a level and then popping exactly that many nodes. Everything collected in that inner loop belongs to a single level, so zigzag order, the rightmost node, level maxima and level averages are each a small change to what you do with that group.

The template

Written for Binary Tree Level Order Traversal (write-up)

from collections import deque

def level_order(root):
    if not root:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):   # exactly this level's nodes
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out

Open in the editor Trace it line by line

Six problems, in learning order

1.Binary Tree Level Order TraversalLeetCode 102Freeze the level size before popping.Medium
2.Binary Tree Zigzag Level Order TraversalLeetCode 103Reverse every other level, or add values to the front of a deque.Medium
3.Binary Tree Right Side ViewLeetCode 199Keep the last node seen on each level.Medium
4.Find Largest Value in Each Tree RowLeetCode 515Track the maximum inside each level's loop.Not in the curated 370 yet.Medium
5.Average of Levels in Binary TreeLeetCode 637Sum each level and divide by the level size.Not in the curated 370 yet.Easy
6.Populating Next Right Pointers in Each NodeLeetCode 116Link each node to the next node popped from the same level.Not in the curated 370 yet.Medium

What usually goes wrong

Reading the queue length after the level's children have already been added.
Using a Python list with pop(0), which costs O(n) per pop; a deque is O(1).
Forgetting to handle an empty tree.

Tree BFS and Level Order, answered

When should I use the tree bfs and level order pattern?

The prompt says level, row, depth order, or right side view. You need the shallowest node that meets some condition. Nodes on the same level have to be linked or compared.

What is the time complexity of tree bfs and level order?

O(n) time, O(w) space, where w is the widest level. Everything collected in that inner loop belongs to a single level, so zigzag order, the rightmost node, level maxima and level averages are each a small change to what you do with that group.

Which problem should I start with for tree bfs and level order?

Start with Binary Tree Level Order Traversal (LeetCode 102, Medium). Freeze the level size before popping. The six problems on this page are in learning order.