Binary Tree Level Order Traversal

Difficulty: Medium Source: NeetCode

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Queue (FIFO) — The data structure that naturally gives us left-to-right level-by-level processing
• BFS — Breadth-first search explores nodes in the exact order we need
• Level Snapshots — The trick of snapshotting the queue size to separate levels

1. BFS with Queue

Intuition

BFS is perfect for level-order traversal. The key insight is that at any point in the BFS, all nodes currently in the queue belong to the same level. By snapshotting len(queue) at the start of each “round,” we can process exactly one level at a time, collect its values, and enqueue the next level’s nodes.

Algorithm

1. If root is null, return []
2. Initialize a queue with root, and an empty result list
3. While the queue is not empty:
   • Snapshot level_size = len(queue)
   • Process exactly level_size nodes, collecting their values into current_level
   • Enqueue each node’s left and right children (if they exist)
   • Append current_level to result
4. Return result

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)  # Number of nodes at this level
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(level_order(root1))  # [[3], [9, 20], [15, 7]]

root2 = build_tree([1])
print(level_order(root2))  # [[1]]

root3 = build_tree([])
print(level_order(root3))  # []

root4 = build_tree([1, 2, 3, 4, 5, 6, 7])
print(level_order(root4))  # [[1], [2, 3], [4, 5, 6, 7]]

Complexity

• Time: O(n) — every node is enqueued and dequeued exactly once
• Space: O(w) — queue holds at most the widest level (up to n/2 nodes for a complete tree)

2. DFS Alternative

Intuition

Level order can also be done with DFS by passing the current level depth. We use a list of lists where index i holds all values at depth i. As DFS explores nodes, it appends each value to the correct list based on depth.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_dfs(root):
    result = []

    def dfs(node, depth):
        if not node:
            return
        if depth == len(result):
            result.append([])  # Start a new level
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 9, 20, None, None, 15, 7])
print(level_order_dfs(root1))  # [[3], [9, 20], [15, 7]]

root2 = build_tree([1, 2, 3, 4, 5, 6, 7])
print(level_order_dfs(root2))  # [[1], [2, 3], [4, 5, 6, 7]]

Complexity

• Time: O(n) — each node visited once
• Space: O(h) for the call stack + O(n) for the result

Common Pitfalls

Not snapshotting the queue length. If you just loop while queue, you’ll mix multiple levels together. The for _ in range(len(queue)) loop is the key mechanism that processes one level at a time.

Using a list instead of deque. list.pop(0) is O(n); deque.popleft() is O(1). For large trees, always use collections.deque for BFS queues.