Binary Tree Level Order Traversal
Understand the problem
Given the root of a binary tree, return its levels from top to bottom — each level is an array of the node values at that level (left to right).
Example:
ts
// 3
// / \
// 9 20
// / \
// 15 7
root = [3, 9, 20, null, null, 15, 7]
output = [[3], [9, 20], [15, 7]]
root = [1]
output = [[1]]
root = null
output = []The result is a 2D array — each element is one level of the tree.
Basic approach
O(n) time, O(h) space — h is the tree heightts
// DFS with a depth parameter — correct, but less intuitive than BFS
function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = []
function dfs(node: TreeNode | null, depth: number) {
if (!node) return
if (result.length === depth) result.push([])
result[depth].push(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
}
dfs(root, 0)
return result
}Why this approach is slow:
DFS can solve it but is less intuitive: you have to pass a depth parameter to put each value in the right level.
BFS handles one level at a time naturally because the queue visits nodes breadth-first.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.