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
rootnode representing the head of a Binary Tree (TreeNode). Can be empty (None). - Output: A list where index
[i]contains all values at depthi. - 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
- Initialization: Create a result list
resand initialize a queue (deque) with the root node if it exists. If root is None, return empty immediately. - 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
levelto store values at this depth.
- Capture the current level size by taking
- Node Processing: Iterate exactly
sizetimes (the number of nodes currently in queue):- Pop the leftmost node from the queue (
node). - Append its value to
level. - If
node.leftexists, append it to the queue. - If
node.rightexists, append it to the queue.
- Pop the leftmost node from the queue (
- Finalization: After processing all nodes in this level (loop finishes), append
leveltores. Repeat until empty.
Complexity Analysis
- Time Complexity: where is the number of nodes. We visit every node exactly once, performing constant time operations per node (enqueue/dequeue).
- Space Complexity: where 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 .
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 (
rootis 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.