LeetCode 102: Binary Tree Level Order Traversal Solution in Python Explained

Problem Statement

In LeetCode 102, you’re given the root of a binary tree. Your task is to return its level-order traversal—a list where each element is a list of node values at each level, visited left to right. This builds on symmetry checks from LeetCode 101: Symmetric Tree, shifting focus to breadth-first exploration rather than mirroring.

Constraints

• Number of nodes: 0 <= n <= 2000
• Node values: -1000 <= Node.val <= 1000

Example

Let’s see some cases:

Copy codeInput: root = [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Output: [[3],[9,20],[15,7]]
Explanation: Level 0: [3], Level 1: [9,20], Level 2: [15,7].

Copy codeInput: root = [1]
Output: [[1]]
Explanation: Single level with one node.

Copy codeInput: root = []
Output: []
Explanation: Empty tree, no levels.

These examples show we’re collecting nodes by level.

Understanding the Problem

How do you solve LeetCode 102: Binary Tree Level Order Traversal in Python? Take root = [3,9,20,null,null,15,7]. We need [[3],[9,20],[15,7]]—level 0 (3), level 1 (9,20), level 2 (15,7). This isn’t a BST validation like LeetCode 98: Validate Binary Search Tree; it’s about breadth-first traversal. We’ll use: 1. Queue-Based BFS: O(n) time, O(w) space—our best solution. 2. Recursive DFS with Levels: O(n) time, O(h) space—an alternative.

Let’s dive into the primary solution.

Solution 1: Queue-Based BFS Approach (Primary)

Explanation

Queue-Based BFS uses a queue to process nodes level-by-level, adding children as it goes. For each level, collect all node values, then enqueue their children for the next level. It’s the best solution due to its natural fit for level-order traversal, efficiency, and clarity in separating levels.

For [3,9,20,null,null,15,7]:

• Level 0: Queue [3], pop 3, add [9,20].
• Level 1: Queue [9,20], pop 9,20, add [15,7].
• Level 2: Queue [15,7], pop 15,7, no children.
• Result: [[3],[9,20],[15,7]].

Step-by-Step Example

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

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

Goal: Return [[3],[9,20],[15,7]].

• Start: queue = deque([3]), result = [].
• Step 1: Level 0.
• Queue size = 1, level = [].
• Pop 3, level = [3], add 9,20 → queue = [9,20].
• result = [[3]].
• Step 2: Level 1.
• Size = 2, level = [].
• Pop 9, level = [9], no children.
• Pop 20, level = [9,20], add 15,7 → queue = [15,7].
• result = [[3],[9,20]].
• Step 3: Level 2.
• Size = 2, level = [].
• Pop 15, level = [15], no children.
• Pop 7, level = [15,7], no children.
• result = [[3],[9,20],[15,7]].
• Finish: Return [[3],[9,20],[15,7]].

Example 2: root = [1]

Goal: Return [[1]].

• Start: queue = deque([1]), result = [].
• Step 1: Level 0.
• Size = 1, level = [1], no children.
• result = [[1]].
• Finish: Return [[1]].

Example 3: root = []

Goal: Return [].

• Start: queue = deque([]).
• Step 1: Queue empty, result = [].
• Finish: Return [].

How the Code Works (Queue-Based BFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codefrom collections import deque

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

def levelOrder(root: TreeNode) -> list[list[int]]:
    # Line 1: Check if root is null
    if not root:
        # If root is None, return empty list (e.g., [])
        return []

    # Line 2: Initialize result list
    result = []
    # Stores level lists (e.g., initially [])

    # Line 3: Initialize queue with root
    queue = deque([root])
    # deque for efficient popping/appending (e.g., [3])
    # Starts with root node

    # Line 4: Process levels while queue has nodes
    while queue:
        # Continues until all levels are processed (e.g., queue not empty)

        # Line 5: Get number of nodes in current level
        level_size = len(queue)
        # Size of current level (e.g., 1 for [3], 2 for [9,20])

        # Line 6: Initialize list for current level
        level = []
        # Collects values for this level (e.g., initially [])

        # Line 7: Process all nodes in current level
        for _ in range(level_size):
            # Loops level_size times (e.g., 1, then 2)

            # Line 8: Pop node from queue
            node = queue.popleft()
            # Removes and gets next node (e.g., 3, then 9, 20)

            # Line 9: Add node value to level
            level.append(node.val)
            # Adds value to current level (e.g., level=[3])

            # Line 10: Add left child if exists
            if node.left:
                queue.append(node.left)
                # Enqueues left child (e.g., 9 for root=3)

            # Line 11: Add right child if exists
            if node.right:
                queue.append(node.right)
                # Enqueues right child (e.g., 20 for root=3)

        # Line 12: Add completed level to result
        result.append(level)
        # Adds level list to result (e.g., [[3]], then [[3],[9,20]])

    # Line 13: Return final level-order traversal
    return result
    # Returns complete list (e.g., [[3],[9,20],[15,7]])

This detailed breakdown clarifies how queue-based BFS efficiently constructs the level-order traversal.

Alternative: Recursive DFS with Levels Approach

Explanation

Recursive DFS with Levels traverses the tree depth-first, tracking the level of each node and building the result list by appending values to the appropriate level. It’s a flexible alternative, leveraging recursion to visit nodes while organizing by depth.

For [3,9,20,null,null,15,7]:

• DFS: 3 (level 0), 9 (1), 20 (1), 15 (2), 7 (2).
• Result: [[3],[9,20],[15,7]].

Step-by-Step Example (Alternative)

For [3,9,20,null,null,15,7]:

• Start: result = [], dfs(3, 0).
• Step 1: 3, level 0, result = [[3]].
• Step 2: 9, level 1, result = [[3],[9]].
• Step 3: 20, level 1, result = [[3],[9,20]].
• Step 4: 15, level 2, result = [[3],[9,20],[15]].
• Step 5: 7, level 2, result = [[3],[9,20],[15,7]].
• Finish: Return [[3],[9,20],[15,7]].

How the Code Works (DFS with Levels)

Copy codedef levelOrderDFS(root: TreeNode) -> list[list[int]]:
    result = []
    def dfs(node: TreeNode, level: int):
        if not node:
            return
        if len(result) <= level:
            result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

Complexity

• Queue-Based BFS:
• Time: O(n) – visits each node once.
• Space: O(w) – queue size, w = max width.
• Recursive DFS with Levels:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.

Efficiency Notes

Queue-Based BFS is the best solution with O(n) time and O(w) space, perfectly suited for level-order traversal—Recursive DFS with Levels matches time complexity with O(h) space, offering a recursive alternative that’s adaptable to level tracking.

Key Insights

• BFS: Level-by-level naturally.
• DFS: Depth-first with level index.
• Order: Left to right preserved.

Additional Example

For root = [1,2,3,4,5]:

• Goal: [[1],[2,3],[4,5]].
• BFS: Level 0: [1], Level 1: [2,3], Level 2: [4,5].

Edge Cases

• Empty Tree: [] → [].
• Single Node: [1] → [[1]].
• Skewed Tree: [1,2,3] → [[1],[2],[3]].

Both solutions handle these well.

Final Thoughts

LeetCode 102: Binary Tree Level Order Traversal in Python is a classic traversal challenge. The Queue-Based BFS solution shines with its efficiency and clarity, while Recursive DFS with Levels offers a recursive twist. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for a different order or LeetCode 101: Symmetric Tree for symmetry checks. Ready to practice? Solve LeetCode 102 on LeetCode with [3,9,20,null,null,15,7], aiming for [[3],[9,20],[15,7]]—test your skills now!