Walk a tree one level at a time with a queue, so every node at the same depth gets grouped and handled together.

Earn the full sheet below.

When to reach for it

• Naturally grouped by level, row, or depth.
• Compare or connect nodes at the same depth.
• DFS works, but BFS groups by depth for free.
• 'Level by level' is practically this pattern's name.

What's on the sheet

The queue levels the tree for you. Step 3 is what you do with each level.

1. Set Up. Queue starts with the root; result collects levels.
2. Snapshot the Level. Freeze len(queue) first; it changes as you pop.
3. Pop and process. Your problem happens here, one node at a time.
4. Close the Level. One sublist per level, until the queue drains.

Watch out

• Snapshot len(queue) into the for loop's range before you start popping. Checking queue length mid-loop is wrong, since enqueuing children changes it as you go.
• Check node.left and node.right for None separately before queueing them. Queue a None node and the next pop crashes on node.val.
• Zigzag traversal doesn't change the BFS shape, it only reverses every other completed level before appending it.

How to earn it

Solve half of the Tree Breadth First Search problems on InterviewCrunch and the sheet is yours. Free accounts included. Members can download every sheet right away.

Want to see a finished sheet first? Preview the Two Pointers sample.

Every pattern has a sheet. See the full set.