Tree Traversal Pattern

All lessons

Learn when a tree problem needs breadth-first (level by level) vs depth-first (root to leaf) traversal — and how to carry the right state down or up the recursion.

0/5 practice problems solved

Skip to practice

Recognizing the pattern

Reach for it when you need to

the problem mentions levels, depth, or "closest"/"shortest" in a tree — usually BFS;
the problem needs a path from root to leaf, or a property that depends on ancestors/descendants — usually DFS;
you need to compare a node against everything below it (subtree) — DFS post-order;
you need to compare a node against everything above it (ancestors, valid-range) — DFS pre-order, passing bounds down.

Don't use it when

The structure isn't a tree (has cycles or multiple parents) — that's Graph Traversal, where you must also track visited nodes.
You only need aggregate stats over a sorted sequence, not tree shape — an array pattern may be simpler.
Recursion depth could exceed the call stack on a very unbalanced tree — an explicit stack (iterative DFS) may be required.

Core mental model

A tree traversal is defined by what state travels with it and in which direction. BFS carries a queue of "frontier" nodes and processes one level at a time, so it naturally answers level/shortest-path questions. DFS carries state down through recursion arguments (e.g. a valid range, a running path) and combines children's results back up through return values (e.g. height, or whether a subtree is balanced) — the invariant is that at each node, the function only needs its own value plus what its children return or what its caller passed down.

Typical time: O(n)

Typical space: O(n) worst case

Balanced tree recursion depth: O(log n)

Visual trace

Binary Tree Level Order Traversal on a small BST. BFS processes one full level before moving to the next.

Level 0: visit 5 — Queue starts with the root. Dequeue 5, enqueue its children (3, 8).

Level 1: visit 3, 8 — Dequeue 3 and 8 (both already in the queue from level 0), enqueue 1, 4, 9.

Scroll the diagrams sideways to see all of them.

Worked example: Binary Tree Level Order Traversal

Root 5, left subtree 3 (children 1, 4), right subtree 8 (right child 9). Process one queue's worth of nodes per level.

Step-by-step trace of Binary Tree Level Order Traversal
Level	Queue at start	Output	Enqueued next
0	[5]	[5]	[3, 8]
Key step: 1	[3, 8]	[3, 8]	[1, 4, 9]
2	[1, 4, 9]	[1, 4, 9]	[]

Invariant: Before processing level k, the queue contains exactly the nodes at depth k, in left-to-right order.

Reusable template

The shape to adapt for a new problem in this pattern.

python

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Common mistakes

Using a plain queue without snapshotting len(queue) at the top of the loop, which mixes two levels together.
Passing valid-range bounds by value but forgetting to narrow them per side when validating a BST (must tighten, not just pass through).
Confusing pre-order (process before recursing) with post-order (process after, using children's results) — pick based on whether you need the answer before or after visiting children.
Recursing without a base case for a null node, causing a crash instead of returning a neutral value (0, True, etc.).
Assuming a tree is balanced when computing recursion depth/complexity — a skewed tree degrades to O(n) depth.

Practice: easy → medium → timed check

Solve in order; each step adds one decision to the same pattern.

1. Maximum Depth of Binary Tree
Easy
Not solved yet
Combine children's results upward
Solution for Maximum Depth of Binary Tree Practice Maximum Depth of Binary Tree
2. Binary Tree Level Order Traversal
Medium
Not solved yet
BFS, one level at a time
Solution for Binary Tree Level Order Traversal Practice Binary Tree Level Order Traversal
3. Validate Binary Search Tree
Medium
Not solved yet
Pass a tightening valid range down
Solution for Validate Binary Search Tree Practice Validate Binary Search Tree
4. Lowest Common Ancestor of a BST
Medium
Not solved yet
Use BST ordering to prune the search
Solution for Lowest Common Ancestor of a BST Practice Lowest Common Ancestor of a BST
5. Binary Tree Zigzag Level Order Traversal
Medium
Not solved yet
BFS with a per-level direction flag
Solution for Binary Tree Zigzag Level Order Traversal Practice Binary Tree Zigzag Level Order Traversal

Final timed check

Run a 30-minute mock covering this pattern; state the invariant before coding, then finish with complexity and edge cases.

Start timed mock

Next lesson

Graph Traversal

Continue