You sweep the tree one level at a time with a queue. Every node at the same depth gets grouped and handled together.

Earn the full sheet below.

When to use it

• The answer groups by level, row, or depth.
• You 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. The queue starts with the root.
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. Each level lands as one sublist.

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 and the sheet is yours. A free account works fine, and everyone earns their sheets the same way.

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

Every pattern has a sheet. See the full set.