Coding Interview PatternsBinary Tree Level Order Traversal II
MediumTree Breadth-First Search
Binary Tree Level Order Traversal II
Explanation & Solution
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).
Examples
Example 1:
```tree
[3, 9, 20, null, null, 15, 7]
`
Input:root = [3, 9, 20, null, null, 15, 7]
0
3
1
9
2
20
3
null
4
null
5
15
6
7
Output: [[15, 7], [9, 20], [3]]
Explanation: The bottom-up level order traversal gives the deepest level first: [15, 7], then [9, 20], then [3].
Example 2:
```tree
[1]
`
Input:root = [1]
0
1
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints
- The number of nodes in the tree is in the range
[0, 2000] -1000 <= Node.val <= 1000
Approach
Tree Breadth-First Search pattern
1. Base Case
- If
rootisnull: - Return
[] - Reason:
- An empty tree has no levels to traverse
2. Initialize BFS
- Create a
resultarray to store levels - Create a
queueinitialized with the root node
3. Process Level by Level
- While the queue is not empty:
- Record the current
levelSize(number of nodes at this level) - Create an empty
levelarray - Loop
levelSizetimes: - Dequeue a node from the front
- Push its value to
level - Enqueue its left child if it exists
- Enqueue its right child if it exists
4. Insert at Front
- After processing each level, use
result.unshift(level)instead ofresult.push(level) - This ensures the deepest level ends up first in the result
5. Return the Result
- The result array now contains levels from bottom to top
Key Insight
- This is standard BFS level-order traversal with one twist: insert each level at the front of the result array instead of the back
- Alternatively, you could do a normal level-order traversal and reverse the result at the end
Time
O(n)visit each node onceSpace
O(n)for the queue and result arrayVisualization
Input:
DFS Traversal[3, 9, 20, 15, 7]
output0
Press play to start DFS traversal
CurrentIn stackComplete
11 steps