Practice Binary Tree Level Order Traversal
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Source: Binary Tree Level Order Traversal on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
root = [3,9,20,null,null,15,7]
[[3],[9,20],[15,7]]
# Example 2
root = [1]
[[1]]
# Example 3
root = []
[]
Constraints
How to solve Binary Tree Level Order Traversal
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A queue processed in rounds, where you read the queue size before the round begins and dequeue exactly that many nodes, separates the breadth-first order into levels without any depth bookkeeping.
Why brute force is not enough
Compute the depth of every node and bucket values by depth, which is correct but makes two passes, or re-traverse the whole tree once per level to collect level k. The second variant is O(n * h), quadratic for a skewed tree of 2000 nodes.
Approach
- If the root is missing, return an empty list.
- Start a queue containing only the root. Invariant: at the beginning of every round, the queue holds exactly the nodes of one level, ordered left to right.
- For each round, snapshot the queue size, then dequeue exactly that many nodes, appending each value to the current level list and enqueuing each present child, left before right.
- Append the level list to the result and repeat until the queue is empty.
- The depth-first alternative recurses with a depth argument and appends each value to the list at that depth, creating it when first reached; visiting left before right preserves order.
Walkthrough of Example 1
root = [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]
- The queue holds 3. Round size is 1: dequeue 3 into the level list and enqueue its children 9 and 20. Level: 3.
- The queue holds 9, 20. Round size is 2: dequeue 9 (no children), then 20, enqueuing 15 and 7. Level: 9, 20.
- The queue holds 15, 7. Round size is 2: dequeue both; neither has children. Level: 15, 7.
- The queue is empty, so the result is the three levels 3, then 9, 20, then 15, 7.
Time and space
Time O(n) · Space O(w). n is the number of nodes, each enqueued and dequeued once; w is the maximum width, which bounds the queue and can reach about n / 2 for a full tree.
Interview pitfalls
- Reading the queue size inside the loop condition so it changes as children are added, which merges adjacent levels.
- Enqueuing missing children and dereferencing them later.
- Returning a list containing one empty level for an empty tree; the expected result is an empty list.
- Popping from the front of a plain dynamic array, which is O(n) per pop and makes the traversal quadratic in some languages.
- Using a stack instead of a queue, which gives a depth-first order that happens to look right on tiny examples.
Follow-up questions interviewers ask
- Produce zigzag order, bottom-up order, or just the rightmost value of each level.
- Return the average of each level, or the level with the largest sum.
- Apply level order to a graph; what extra state is needed to avoid revisiting nodes?
Further reading on the technique: Breadth-first search
Related LeetCode Problems
Practice more problems similar to Binary Tree Level Order Traversal.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.