March 24
Binary Tree Level Order Traversal
How to traverse a tree level by level with a queue and clearly separate what belongs to the current level before moving down.
Trees Intermediate 18 min TypeScript
Given the root of a binary tree, return its values level by level.
The result should be an array of arrays, where each inner array contains the values from one level of the tree.
Example:
Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
What to notice before coding
- The problem asks you to group by level.
- [`BFS`](/glossary/bfs) visits the tree in breadth, which matches the output structure exactly.
- The [`queue`](/glossary/queue) needs to know where the current level ends.
Common mistakes
- putting every value into one flat array
- iterating over a queue while it grows and mixing two levels into the same group
Step 1 - Read the output format carefully
The result is not only asking you to traverse the tree.
It asks you to:
- separate values by level
That is already a strong hint toward BFS.
Step 2 - Write a baseline that groups by depth
A valid baseline is DFS with a level parameter:
- when you enter a node, add its value to
result[level] - call left and right with
level + 1
It works, but the idea of level stays more indirect.
Step 3 - Notice why BFS fits better
In BFS:
- the queue stores the exploration frontier
- nodes arrive in the same order the levels appear
In other words, the traversal strategy already has the same shape as the answer.
Step 4 - Delimit the current level
The important detail is:
- before processing a level, store
queue.length
That number tells you how many nodes belong to the current level.
Any children pushed during the loop belong to the next level.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function levelOrder(root) {
// root is an object like { val: number, left: ..., right: ... } or null
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(n)
Solution 1 - DFS grouping by depth
Good baseline because it returns the correct format and reinforces the depth idea.
export function levelOrder(root) {
const result = []
function dfs(node, level) {
if (node === null) {
return
}
if (!result[level]) {
result[level] = []
}
result[level].push(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
}
dfs(root, 0)
return result
}It works. But BFS makes the layer idea much more explicit.
Solution 2 - Level-order BFS with a queue
Now the traversal matches the required output naturally.
export function levelOrder(root) {
if (root === null) {
return []
}
const result = []
const queue = [root]
while (queue.length > 0) {
const levelSize = queue.length
const level = []
for (let index = 0; index < levelSize; index += 1) {
const node = queue.shift()
level.push(node.val)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
result.push(level)
}
return result
}The most important part here is the frontier of the current level.
What to say in the interview
A strong short explanation would be:
Since the answer asks for groups by level,
BFSfits naturally. I use aqueueand, before processing each layer, I store the current queue length. That tells me how many nodes belong to the current level. Children are added afterward, so they stay for the next round.
That shows that you:
- read the output format as an algorithm hint
- understand the frontier idea in
BFS - can explain why levels do not get mixed
When this pattern shows up again
The same pattern comes back when you need to:
- traverse a tree by layers
- group values by level
- use a
queueto explore breadth - solve zigzag, right side view, and level averages
The point is not memorizing
levelOrder.
The point is noticing when the output format almost chooses the algorithm for you.