LeetCode Solutions Blog

Binary Tree Level Order Traversal II

Number: 107

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values (i.e., from left to right, level by level from leaf to root).

Key Insights

Use a breadth-first search (BFS) to traverse the tree level by level.
Utilize a queue to manage nodes during the traversal.
Collect the values of nodes for each level into a temporary list.
To achieve bottom-up order, either insert each level's list at the beginning of the result list or reverse the final list after a standard level order traversal.

Space and Time Complexity

Time Complexity: O(n) — Each node is visited exactly once. Space Complexity: O(n) — The space is used by the queue and the output list, where n is the number of nodes.

Solution

We adopt a BFS strategy using a queue. Starting from the root, we visit each node level by level. For each level, we collect the values into a temporary list. We then insert this list at the beginning of the result list, ensuring that lower levels appear before higher ones. This method efficiently handles the problem while meeting the required bottom-up order without needing additional reversal operations.

Code Solutions

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

from collections import deque

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        # Return an empty list if the tree is empty
        if not root:
            return []
        result = []
        # Use a deque for efficient popping from the left
        queue = deque([root])
        
        # Process nodes level by level
        while queue:
            level_length = len(queue)
            current_level = []
            # Loop through nodes in the current level
            for _ in range(level_length):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # Insert the current level at the beginning of the result list
            result.insert(0, current_level)
        return result