Any tree question containing the words “level”, “depth”, “row”, “nearest”, or “width” is a breadth-first traversal in disguise. DFS visits a whole branch before its siblings, so it never has a level assembled in one place; BFS processes the tree in horizontal layers, which is exactly the shape those questions ask about.

There is one template. Once you can write it without thinking, roughly a dozen Medium problems become five-minute problems.

What you’ll learn

• The level-snapshot trick — the single line that turns a flat queue into “one iteration per level”.
• Why collections.dequecollections.deque and not a list (and what it costs if you get it wrong).
• The five mutations of the template that cover the whole level-order family.
• Four real LeetCode problems solved here in the browser: 102, 199, 103, and 111.

The cue

The template

from collections import deque
 
 
def level_order(root):
    if not root:                       # always handle the empty tree first
        return []
 
    result = []
    queue = deque([root])
 
    while queue:
        level_width = len(queue)       # <-- THE snapshot: freeze this level's size
        level = []
 
        for _ in range(level_width):   # consume exactly this level
            node = queue.popleft()
            level.append(node.val)
 
            if node.left:              # children form the NEXT level
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
 
        result.append(level)
 
    return result

from collections import deque
 
 
def level_order(root):
    if not root:                       # always handle the empty tree first
        return []
 
    result = []
    queue = deque([root])
 
    while queue:
        level_width = len(queue)       # <-- THE snapshot: freeze this level's size
        level = []
 
        for _ in range(level_width):   # consume exactly this level
            node = queue.popleft()
            level.append(node.val)
 
            if node.left:              # children form the NEXT level
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
 
        result.append(level)
 
    return result

Everything in the level-order family is this template with one of the inner lines changed.

How it works

Level by level, the queue holds exactly one complete level at the top of each whilewhile iteration. The inner forfor drains that level and, in the process, enqueues the entire next level behind it.

  graph TD
    A["3"] --> B["9"]
    A --> C["20"]
    C --> D["15"]
    C --> E["7"]

For the tree above:

Time and space complexity

For a balanced tree the widest level holds about $n/2$ nodes, so space is $O(n)$. For a degenerate “linked list” tree the queue never holds more than one node, so space is $O(1)$ — the exact opposite of DFS recursion, which is $O(\log n)$ on a balanced tree and $O(n)$ on a degenerate one.

The variant map

Practice — real LeetCode problems

Each exercise is the real LeetCode problem with its real method signature. TreeNodeTreeNode and a build(...)build(...) helper (which turns LeetCode’s level-order array notation into an actual tree) are provided in the editor. Write the body, press Run, and match the expected output.

LC 102 — Binary Tree Level Order Traversal · Medium

Problem. Given the rootroot of a binary tree, return the values of its nodes grouped by level, from left to right, one list per level.

Constraints. 0 <= number of nodes <= 20000 <= number of nodes <= 2000, -1000 <= Node.val <= 1000-1000 <= Node.val <= 1000.

Examples. [3,9,20,null,null,15,7][3,9,20,null,null,15,7] gives [[3],[9,20],[15,7]][[3],[9,20],[15,7]] · [1][1] gives [[1]][[1]] · [][] gives [][]

LC 199 — Binary Tree Right Side View · Medium

Problem. Given the rootroot of a binary tree, imagine standing to its right. Return the values of the nodes you can see, ordered top to bottom.

Constraints. 0 <= number of nodes <= 1000 <= number of nodes <= 100.

Examples. [1,2,3,null,5,null,4][1,2,3,null,5,null,4] gives [1,3,4][1,3,4] · [1,null,3][1,null,3] gives [1,3][1,3] · [][] gives [][]

LC 103 — Binary Tree Zigzag Level Order Traversal · Medium

Problem. Return the level-order traversal, but alternate direction per level: level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on.

Constraints. 0 <= number of nodes <= 20000 <= number of nodes <= 2000.

Examples. [3,9,20,null,null,15,7][3,9,20,null,null,15,7] gives [[3],[20,9],[15,7]][[3],[20,9],[15,7]] · [1][1] gives [[1]][[1]] · [][] gives [][]

LC 111 — Minimum Depth of Binary Tree · Easy

Problem. Return the number of nodes along the shortest path from the root down to the nearest leaf. A leaf is a node with no children.

Constraints. 0 <= number of nodes <= 10^50 <= number of nodes <= 10^5.

Examples. [3,9,20,null,null,15,7][3,9,20,null,null,15,7] gives 22 · [2,null,3,null,4,null,5,null,6][2,null,3,null,4,null,5,null,6] gives 55 · [][] gives 00

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Empty tree (root is Noneroot is None) — must return [][] / 00, and must not enqueue NoneNone.
• Single node — one level, and it is also a leaf. LC 111 must return 11.
• One-child nodes — the killer for LC 111: a node with one child is not a leaf.
• Completely one-sided tree ([1,null,2,null,3][1,null,2,null,3]) — every level has width 1; verifies your snapshot logic doesn’t assume two children.
• Duplicate values — never identify nodes by valval; use the node objects themselves.
• Negative values — don’t initialise a per-level max to 00; use the first element or float("-inf")float("-inf").
• Very wide tree — mention the $O(w)$ queue memory before the interviewer does.

Recap

• Tree BFS = a dequedeque, plus one snapshot line (level_width = len(queue)level_width = len(queue)) that turns a flat queue into per-level iteration.
• The whole level-order family is that template with one inner line changed: keep all values, keep one value, flip the assembly order, exit early, or carry extra state per node.
• BFS for “per level” and “nearest”; DFS for paths and subtree properties. Minimum depth is BFS (early exit); maximum depth is DFS.
• $O(n)$ time, $O(w)$ space — and deque.popleft()deque.popleft(), never list.pop(0)list.pop(0).
• To reverse or zigzag, change the assembly, never the traversal.

Next: BST Patterns — what changes once the tree is ordered, and why an in-order walk is the only tool you need for a surprising number of problems.