Problem 25 · Trees

Binary Tree Level Order Traversal

MediumClassic DSA & systems

01Problem

Return the values of a binary tree level by level, left to right, as a list of lists.

02Key insight

BFS with a queue, draining exactly len(queue) nodes per iteration so each loop iteration is one level.

03Solution

solution.pypython23 lines

from __future__ import annotations
from collections import deque
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            queue.extend(child for child in (node.left, node.right) if child)
        levels.append(level)
    return levels

Try it first.

TimeO(n)

SpaceO(w) where w = max width

tests.py · 3 passing

tests.pypython5 lines

T = TreeNode
root = T(3, T(9), T(20, T(15), T(7)))
assert level_order(root) == [[3], [9, 20], [15, 7]]
assert level_order(None) == []
assert level_order(T(1, None, T(2, T(3)))) == [[1], [2], [3]]

04Staff-level follow-up

Tree is very wide (millions of nodes per level)? Queue memory is O(width); DFS with a depth parameter uses O(height) stack instead and still groups by depth.