Domain 2MediumCORE

Binary Tree Level Order Traversal

Goal: Traverse a binary tree level by level, from top to bottom. Within each level, traverse nodes from left to right. Return this as a list of lists (a 2D array).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Tree#Breadth-first Search

102. Binary Tree Level Order Traversal

Model: qwen3.5:9b
Topics: Tree,Breadth-first Search
FAANG asked: 1
Acceptance rate: 57.0%


Problem Breakdown

Goal: Traverse a binary tree level by level, from top to bottom. Within each level, traverse nodes from left to right. Return this as a list of lists (a 2D array).

  • Input: A root node representing the head of a Binary Tree (TreeNode). Can be empty (None).
  • Output: A list where index [i] contains all values at depth i.
  • Constraints & Edge Cases:
    • Empty tree: Return an empty list.
    • Single node: Returns one inner list with that value.
    • Node values can be negative; logic doesn’t depend on magnitude, only structure.
    • Tree size up to 2000 nodes (fits easily in memory).

Intuition

The requirement is “level by level.” This immediately signals Breadth-First Search (BFS).

A naive approach might be Depth-First Search (DFS) with a depth counter, pushing values into buckets based on current recursion stack height. While valid, it requires managing state for the current depth at every call or using an explicit map depth -> list.

The most direct way to process level-by-level is using a Queue. We push children as we visit parents. To distinguish when one level ends and another begins (since nodes are added continuously), we need to know how many nodes belong to the current level before processing them. The key insight: len(queue) at the start of each iteration gives us exactly that count for the current layer.

Approach

  1. Initialization: Create a result list res and initialize a queue (deque) with the root node if it exists. If root is None, return empty immediately.
  2. Level Loop: While the queue isn’t empty:
    • Capture the current level size by taking len(queue). This acts as our loop counter for this specific layer only.
    • Create a temporary list level to store values at this depth.
  3. Node Processing: Iterate exactly size times (the number of nodes currently in queue):
    • Pop the leftmost node from the queue (node).
    • Append its value to level.
    • If node.left exists, append it to the queue.
    • If node.right exists, append it to the queue.
  4. Finalization: After processing all nodes in this level (loop finishes), append level to res. Repeat until empty.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of nodes. We visit every node exactly once, performing constant time operations per node (enqueue/dequeue).
  • Space Complexity: O(W)O(W) where WW is the maximum width of the tree (maximum number of nodes at any level), which occurs in the queue and result list simultaneously. In a complete binary tree, this approaches O(N)O(N).

Solution

from collections import deque
from typing import List, Optional

# Definition for a Node. 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: Optional['TreeNode']) -> List[List[int]]:
    if not root:
        return []
    
    res = []
    queue = deque([root])
    
    while queue:
        # Capture current level size to process layer by layer without recursion depth issues
        level_size = len(queue)
        current_level_vals = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level_vals.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        res.append(current_level_vals)
    
    return res

Edge Cases Handled

  • Empty Tree (root is None): Returns [] immediately via the initial check.
  • Single Node: Queue processes root, adds no children, loop finishes once, returns [ [val] ].
  • Skewed Trees (Left or Right only): Logic holds because queue size tracks strictly by level count regardless of tree shape; it doesn’t rely on balanced structure.
  • Negative Values: Appended directly to list; logic treats values as opaque integers.