How do you solve Binary Tree Level Order Traversal II on LeetCode?

Binary Tree Level Order Traversal II (LeetCode #107) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a queue for level order traversal is essential.

What is the brute force solution for Binary Tree Level Order Traversal II?

The brute force approach for Binary Tree Level Order Traversal II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves performing a level order traversal of the binary tree and then reversing the result to achieve the bottom-up order. This is straightforward but not efficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Tree Level Order Traversal II?

Binary Tree Level Order Traversal II uses the following concepts: Tree, Breadth-First Search, Binary Tree. The recommended patterns to study are: Breadth-First Search, Queue.

What are the interview tips for Binary Tree Level Order Traversal II?

Always clarify the output format before starting. Think about edge cases like empty trees or trees with only one node. Practice explaining your thought process as you code.

What are common mistakes when solving Binary Tree Level Order Traversal II?

Not handling the case of an empty tree properly. Confusing level order with depth-first traversal.

#107

Binary Tree Level Order Traversal II

Medium

TreeBreadth-First SearchBinary TreeBreadth-First SearchQueue

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a queue for level order traversal but directly constructs the result in reverse order. This avoids the need for a separate reversal step, making it more efficient.

⚙️

Algorithm

3 steps

1Step 1: Initialize a queue and a result list.
2Step 2: Perform a level order traversal, but insert each level at the beginning of the result list.
3Step 3: Continue until all levels are processed.

solution.py20 lines

1# Full working Python code
2from collections import deque
3
4def levelOrderBottom(root):
5    if not root:
6        return []
7    result = []
8    queue = deque([root])
9    while queue:
10        level_size = len(queue)
11        level_nodes = []
12        for _ in range(level_size):
13            node = queue.popleft()
14            level_nodes.append(node.val)
15            if node.left:
16                queue.append(node.left)
17            if node.right:
18                queue.append(node.right)
19        result.insert(0, level_nodes)
20    return result

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) due to the storage of the result and the queue, which can hold up to n nodes in the worst case.

1Using a queue for level order traversal is essential.
2Inserting levels at the beginning of the result list is more efficient than reversing later.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.