Binary Tree Level Order Traversal

MediumTree BFSBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary tree. Return its node values level by level: a list of lists where the i-th inner list holds every value at depth i, read left to right. The root is depth 0. An empty tree returns an empty list. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

root = [3,9,20,null,null,15,7] returns [[3],[9,20],[15,7]]

Depth 0 holds only the root 3. Depth 1 holds 9 and 20, left to right. Depth 2 holds 20's children 15 and 7, since 9 has no children.

root = [] returns []

There are no nodes, so there are no levels to report.

root = [1,2,3,4,null,null,5] returns [[1],[2,3],[4,5]]

4 and 5 sit on the same level under different parents.

4 is the left child of 2 and 5 is the right child of 3. They have different parents but the same depth, so they share one inner list.

Constraints

0 <= number of nodes <= 2000

Hints

Hint 1

What data structure naturally processes nodes in order of distance from the root?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Visit the tree one level at a time with a queue that starts with just the root. At the start of each round the queue holds exactly one level, so record its size, pop that many nodes, collect their values in order, and push each popped node's non-null children, left then right. Append that list and repeat until the queue is empty. O(n) time, O(n) space for the queue and the output.

Time

O(n)

Space

O(n)

Pitfall

Using the live queue length as the inner loop bound while you push children, which blends the next level into the current one. Snapshot the size first, and return [] rather than [[]] for an empty tree.

Solutions

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

from collections import deque

class Solution:
    def levelOrder(self, root):
        result = []
        if not root:
            return result
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result