LeetCode 107: Binary Tree Level Order Traversal II Solution in Python Explained

Problem Statement

In LeetCode 107, you’re given the root of a binary tree. Your task is to return its level-order traversal as a list of lists, where each inner list contains node values at a given level from left to right, ordered from the bottom (leaf level) to the top (root level). This builds on LeetCode 102: Binary Tree Level Order Traversal, reversing the level order, and differs from tree construction like LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal.

Constraints

• Number of nodes: 0 <= n <= 10^4
• Node values: -100 <= Node.val <= 100

Example

Let’s see some cases:

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

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

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

These examples show we’re collecting levels bottom-up.

Understanding the Problem

How do you solve LeetCode 107: Binary Tree Level Order Traversal II in Python? Take root = [3,9,20,null,null,15,7]. We need [[15,7],[9,20],[3]]—leaf level (15,7), middle level (9,20), root level (3). This isn’t a preorder-based construction like LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal; it’s about level-order traversal with a bottom-up twist. We’ll use: 1. Queue-Based BFS with Reversal: O(n) time, O(w) space—our best solution. 2. DFS with Level Tracking: O(n) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Queue-Based BFS with Reversal Approach

Explanation

Queue-Based BFS with Reversal processes the tree level-by-level using a queue, collecting node values in standard top-down order, then reverses the result to achieve bottom-up order. For each level, enqueue children and build the level list, adding it to the result. Finally, reverse the entire result. This is the best solution due to its efficiency, clarity, and direct adaptation of level-order traversal, with a simple reversal step to meet the bottom-up requirement.

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

• Top-down: [[3],[9,20],[15,7]].
• Reverse: [[15,7],[9,20],[3]].

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 [[15,7],[9,20],[3]].

• Start: queue = deque([3]), result = [].
• Step 1: Level 0.
• 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]].
• Step 4: Reverse result = [[15,7],[9,20],[3]].
• Finish: Return [[15,7],[9,20],[3]].

Example 2: root = [1]

Goal: Return [[1]].

• Start: queue = deque([1]), result = [].
• Step 1: Level 0.
• Size = 1, level = [1], no children.
• result = [[1]].
• Step 2: Reverse (no change), 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 with Reversal) – 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 levelOrderBottom(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 top-down (e.g., initially [])

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

    # 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 level to result
        result.append(level)
        # Adds level list (e.g., [[3]], then [[3],[9,20]])

    # Line 13: Reverse result for bottom-up order
    result.reverse()
    # Flips top-down to bottom-up (e.g., [[3],[9,20],[15,7]] → [[15,7],[9,20],[3]])

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

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

Alternative: DFS with Level Tracking Approach

Explanation

DFS with Level Tracking traverses the tree depth-first, tracking each node’s level and building the result list from top-down, then reverses it. It uses recursion to visit nodes, appending values to level-specific lists. This is a versatile alternative, adapting depth-first traversal to level organization with a final reversal.

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

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

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]].
• Step 6: Reverse result = [[15,7],[9,20],[3]].
• Finish: Return [[15,7],[9,20],[3]].

How the Code Works (DFS with Level Tracking)

Copy codedef levelOrderBottomDFS(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[::-1]  # Reverse using slice

Complexity

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

Efficiency Notes

Queue-Based BFS with Reversal is the best solution with O(n) time and O(w) space, naturally suited for level-order traversal with a simple reversal—DFS with Level Tracking matches time complexity with O(h) space, offering a recursive approach that’s adaptable but requires post-processing.

Key Insights

• Bottom-Up: Reverse top-down order.
• BFS: Level-by-level traversal.
• DFS: Depth-first with level reversal.

Additional Example

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

• Goal: [[4,5],[2,3],[1]].
• BFS: Top-down [[1],[2,3],[4,5]], reverse → [[4,5],[2,3],[1]].

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 107: Binary Tree Level Order Traversal II in Python is a fun twist on level-order traversal. The Queue-Based BFS with Reversal solution excels with its efficiency and clarity, while DFS with Level Tracking offers a recursive alternative. Want more? Try LeetCode 102: Binary Tree Level Order Traversal for top-down order or LeetCode 94: Binary Tree Inorder Traversal for inorder basics. Ready to practice? Solve LeetCode 107 on LeetCode with [3,9,20,null,null,15,7], aiming for [[15,7],[9,20],[3]]—test your skills now!