How do you approach Binary Tree Level Order Traversal?

Use BFS (breadth-first search) with a queue.

What is the time complexity of Binary Tree Level Order Traversal?

Time complexity: O(n). Space complexity: O(n) for the queue.

What are common mistakes on Binary Tree Level Order Traversal?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Binary Tree Level Order Traversal

MediumData Structures

Description

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). **Note:** The tree is represented as an array in level-order (BFS) format, where `null` represents missing nodes. Return a 2D array where each inner array contains the values at that level.

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Example 2

Input: root = [1]

Output: [[1]]

Example 3

Input: root = []

Output: []

Constraints

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

Binary Tree Level Order Traversal: approach, complexity and pitfalls

A medium trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Use BFS (breadth-first search) with a queue.
Process nodes level by level - track the size of each level.
Build the tree from the array first, then perform BFS.

The optimal approach

Show the approach: BFS with Queue

Build the tree from the level-order array, then use BFS. Process nodes level by level by tracking the queue size at the start of each level.

Time: O(n)
Space: O(n) for the queue

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.