Full lesson preview

Perform BFS level order traversal of a tree

Return the level order traversal (breadth-first) of a binary tree as a list of level-wise node values.

Python practice15 minStacks & QueuesIntermediateLast updated March 27, 2026

Problem statement

Given the root of a binary tree, return its level order traversal as a list of lists where each inner list contains node values at that depth from left to right. If the tree is empty, return an empty list. Use an iterative BFS approach with a queue.

Task

Implement a BFS traversal to collect node values level by level using a queue.

Examples

Example: simple three-node tree

Input

root = TreeNode(1, TreeNode(2), TreeNode(3))

Output

[[1], [2, 3]]

Level 0 has [1]. Level 1 has [2, 3].

Input format

A binary tree passed as the root TreeNode object.

Output format

A list of lists of integers representing node values per level.

Constraints

The number of nodes in the tree is between 0 and 10^4. Node values are integers.

Samples

Sample 1

Input

TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

Output

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

Three levels: root 3, then 9 and 20, then 15 and 7.