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 (
rootisNone). - Node values are integers, potentially negative or zero.
- Max nodes: 2000 (fits within standard integer limits and memory constraints easily).
- Tree can be empty (
Intuition
The core operation required here is Breadth-First Search (BFS) to traverse the tree level by level.
- 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.
- 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).
- Key Decision: To achieve Bottom-Up without inserting elements at index
0of 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
- Handle Empty Case: If
rootisNone, return an empty list immediately. - Initialize BFS Queue: Use a deque for efficient O(1) pops from front and appends to back. Push the root node into it.
- 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_levellist, and push valid left/right children into the back. - Append
current_levelto our main result list after processing all nodes at this depth.
- 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 (
rootisNone): 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.