Skip to main content

102. Binary Tree Level Order Traversal

medium

Return the values of a binary tree level by level, top to bottom, left to right. The canonical BFS introduction problem — patterns from here unlock dozens of tree variants.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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).

Constraints

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

Examples

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
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

BFS with a queue is the natural fit — but you need to know where each level starts and ends.

Hint 2

Snapshot the queue size at the start of each level; that's exactly the number of nodes in this level.

Hint 3

For each level, pop that many nodes, collect their values, and enqueue their children.

Solution approach

Reveal approach

BFS with per-level batching. Use a queue initialized with root (early-return empty if root is null). Loop while the queue is non-empty: snapshot levelSize = queue.length; collect levelSize values into a new list while popping that many nodes from the front of the queue and enqueueing each one's non-null children. Append the level list to the result. After the loop return result. The snapshot trick keeps levels separated cleanly without sentinel values. O(n) time, O(width) extra space for the queue (up to O(n) in the worst case).

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • bfs
  • queue

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Binary Tree Level Order Traversal and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →