102. Binary Tree Level Order Traversal

102

MediumTrees and Binary Search TreesBreadth-first search with a queueLevel-by-level BFS

Binary Tree Level Order Traversal

Given the root of a binary tree, return its level order traversal: a list of levels, where each level is the list of node values from left to right at that depth.

Open official problem prompt ↗

In plain English

Produce the node values grouped into the horizontal rows of the tree, top to bottom, left to right.

Picture it like this

Like reading a corporate org chart one management tier at a time: everyone at the same level before descending to their reports.

Example

Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]
Why: Level 0 is [3], level 1 is [9, 20], and level 2 is [15, 7], each read left to right.

Constraints

The number of nodes is in the range [0, 2000]-1000 <= Node.val <= 1000

Pattern lesson

See the pattern, then code

Level-by-level BFS

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. If you record the queue's size at the start of each iteration, that count is exactly the number of nodes on the current level, so you can carve the stream into levels.

New words, made simpleKnow these before the algorithm

BFS: Breadth-first search: visit nodes in order of distance from the root, nearest first.
Queue (FIFO): First-in, first-out structure that naturally yields nodes in left-to-right, level-by-level order.
Level snapshot: Capturing the queue's current size to know exactly how many nodes belong to the current level.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

DFS with depth tag

Works and is concise, but conceptually less direct for a level-grouped output.

Recurse, passing a depth index, and append each value into result[depth].

Time O(n)Space O(h)

Best choiceQueue-based BFS with size snapshot

Directly mirrors the level structure and is the standard expected answer.

Process the queue in batches sized by the current level's node count.

Time O(n)Space O(n)

The rule we keep true

Invariant

At the top of each while iteration, the queue contains exactly the nodes of one level, in left-to-right order.

Why this is correct

Reasoning

Children are enqueued in left-to-right order right after their parent, so a FIFO queue drains one complete level before any node of the next level appears; snapshotting len(queue) isolates each level.

The algorithm in three movesSay these aloud before coding

1Return [] if root is null

queue=[3] -> level [3]

2Push root into a queue

queue=[9,20] -> level [9,20]

3Loop while the queue is nonempty

queue=[15,7] -> level [15,7]

4Snapshot the queue length as the current level size and pop exactly that many, collecting values and enqueuing their children

5Append the collected level to the result

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

202

153

1 · Readqueue=[3]

2 · AskHow many nodes now?

3 · Update statesize=1

4 · Resultcollect [3]; enqueue 9,20

Key takeaway

Each queue snapshot corresponds to one horizontal level of the tree.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 15-16Empty guard
A null root yields an empty list of levels.
2
Lines 20-21Freeze the level size
Reading len(queue) before the inner loop pins down how many nodes belong to this level, even as we add children.
3
Lines 23-27Emit and expand
Record the value and enqueue existing children left-then-right to preserve order.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty tree returns []
Single node returns [[val]]
Skewed tree returns one node per level

Common beginner mistakes

Calling len(queue) inside the inner loop after appending children, which mixes levels together
Forgetting the empty-root guard and returning [[]]
Enqueuing None children, then crashing on node.val

Check your understanding

Why must we capture len(queue) before the inner for-loop instead of iterating while the queue is nonempty?

PyPython 3 · solution.py

Optimal

1from typing import Optional, List2from collections import deque34# Definition for a binary tree node.5# class TreeNode:6#     def __init__(self, val=0, left=None, right=None):7#         self.val = val8#         self.left = left9#         self.right = right1011class Solution:12    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:13        if not root:14            return []15        result: List[List[int]] = []16        queue = deque([root])17        while queue:18            level = []19            for _ in range(len(queue)):20                node = queue.popleft()21                level.append(node.val)22                if node.left:23                    queue.append(node.left)24                if node.right:25                    queue.append(node.right)26            result.append(level)27        return result

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftMetaBloomberg

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees