MediumTreeBreadth-First SearchBinary Tree

Binary Tree Level Order Traversal

1 approach, code in every language

You are given the root of a binary tree. Return its values grouped by level, where each group holds the values of one depth read from left to right.

The first group contains only the root, the second group contains the root's children, and so on down the tree. The output is a list of lists, one inner list per level, in top-to-bottom order.

This is a classic breadth-first problem: instead of diving deep along one branch, we sweep across the tree one horizontal layer at a time.

Example 1

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

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

Level 0 is the root 3, level 1 is its children 9 and 20, and level 2 is 20's children 15 and 7.

Example 2

Input: root = [1]

Output: [[1]]

A single-node tree produces one level containing just the root.

Constraints

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

BFS with Level-Sized Batches

Process the tree with a queue, handling exactly one level per outer iteration.

Loading animation…

Intuition

Breadth-first search naturally visits nodes in level order, but a plain queue mixes nodes from adjacent levels together. The trick to separating levels is to snapshot the queue's size at the start of each outer loop: that count is exactly how many nodes belong to the current level. We then dequeue precisely that many nodes into one group while enqueuing their children for the next round. Because children are always appended behind the current level, each snapshot cleanly captures one full level before its successors are touched.

Algorithm walkthrough

1Return an empty list if the root is null; otherwise seed a queue with the root.
2While the queue is not empty, read its current length and call that the level size.
3Create a fresh list for this level and loop exactly level-size times.
4On each iteration dequeue a node, add its value to the level list, and enqueue its non-null children.
5After the inner loop, append the completed level list to the result.
6When the queue empties, return the list of levels.

Implementation

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue: deque = deque([root])
        while queue:
            level_size = len(queue)
            level: List[int] = []
            for _ in range(level_size):
                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

Time

O(n)

Space

O(n)

Every node is enqueued and dequeued exactly once. The queue can hold up to the widest level, which is O(n) in the worst case for a full bottom level.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Cable Splice Depths is our own problem on the technique behind Binary Tree Level Order Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free