Domain 2MediumCORE

Binary Tree Level Order Traversal II

We are given the root node of a binary tree and need to return its level order traversal. The critical constraint is that this must be bottom-up, meaning we start from the leaf levels (deepest) up to the root, rather than top-down like standard BFS.

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

107. Binary Tree Level Order Traversal II

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


Problem Breakdown

We are given the root node of a binary tree and need to return its level order traversal. The critical constraint is that this must be bottom-up, meaning we start from the leaf levels (deepest) up to the root, rather than top-down like standard BFS.

  • Input: root - A pointer to the head node of a binary tree (TreeNode).
  • Output: A list of lists where each inner list contains integer values at that specific depth from left-to-right. The outer list is ordered by increasing depth (deepest first).
  • Constraints & Edge Cases:
    • Tree can be empty (root is None).
    • Node values are integers, potentially negative or zero.
    • Max nodes: 2000 (fits within standard integer limits and memory constraints easily).

Intuition

The core operation required here is Breadth-First Search (BFS) to traverse the tree level by level.

  1. Brute Force: One might think of recursively traversing left/right children, calculating depth for each node, storing values in a dictionary keyed by depth, and then sorting/reversing at the end. This adds unnecessary overhead with map lookups or recursion stack management.
  2. Optimization Insight: Standard BFS using a queue naturally processes nodes level-by-level from top to bottom. If we collect these levels into a list during traversal, we get the standard Level Order Traversal (Top-Down).
  3. Key Decision: To achieve Bottom-Up without inserting elements at index 0 of our result array (which is O(k) per insertion leading to O(N^2)), we simply append each level’s values as a new list and perform a single reversal operation on the final output structure. Reversing an N-element list takes O(N), which is negligible compared to traversing the tree nodes themselves, making this approach optimal in terms of time complexity.

Approach

  1. Handle Empty Case: If root is None, return an empty list immediately.
  2. Initialize BFS Queue: Use a deque for efficient O(1) pops from front and appends to back. Push the root node into it.
  3. Level-by-Level Traversal:
    • While the queue is not empty, determine the number of nodes currently in the queue (this represents the current level’s width).
    • Iterate exactly that many times: pop a node from front, add its value to current_level list, and push valid left/right children into the back.
    • Append current_level to our main result list after processing all nodes at this depth.
  4. Finalize: Reverse the accumulated result list in-place or using slicing ([::-1]) before returning.

Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once during BFS traversal. The reversal operation at the end iterates over a total of N elements across all levels, keeping it linear overall.
  • Space Complexity: O(W + L) or effectively O(N).
    • W (Queue size): In the worst case (a complete binary tree), this is proportional to half the nodes in the last level.
    • L (Result storage): We store every node’s value exactly once across all inner lists, totaling O(N).

Solution

from collections import deque
from typing import List, Optional

# 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

def levelOrderBottom(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    queue = deque([root])
    result = []
    
    while queue:
        # Determine the number of nodes at current level
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result.append(current_level)
    
    # Reverse the top-down traversal to get bottom-up order
    return result[::-1]

Edge Cases Handled

  • Empty Tree (root is None): Returns an empty list immediately without entering the loop.
  • Single Node: Queue processes root, adds one level [val], reverses (no change), returns correct output.
  • Skewed Trees (Left-only or Right-only): BFS handles depth-first-like structures correctly by processing nodes as they are added to queue; logic remains O(N).
  • Negative Values: Node values (-1000 <= val) are treated purely as integers in the list, no special handling required.