Binary Tree Level Order Traversal II - Solution & Explanation
Problem Statement
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).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [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 Overview
Problem Overview: Given the root of a binary tree, return the level order traversal of its nodes from bottom to top. Instead of listing levels starting from the root, you collect nodes level by level and return them in reverse order so the deepest level appears first.
Approach 1: Level Order Traversal with Queue and Stack (O(n) time, O(n) space)
This approach performs a standard BFS using a queue. Start by pushing the root into the queue, then repeatedly process nodes level by level. For each level, iterate through the current queue size, pop nodes, record their values, and push their children. Instead of appending each level directly to the result, push the level list onto a stack. After BFS finishes, pop from the stack to build the final bottom‑up order. Every node is visited exactly once, giving O(n) time complexity and O(n) auxiliary space for the queue, stack, and result. This is the most intuitive solution because it mirrors the normal Breadth-First Search traversal while simply reversing the level order.
Approach 2: Recursive Level Order Traversal (O(n) time, O(n) space)
This solution uses DFS recursion while tracking the current depth. Maintain a list of lists where each index corresponds to a tree level. During recursion, if the current depth equals the size of the result list, create a new level container. Insert the node value into the corresponding level, then recursively process the left and right children with depth + 1. Once traversal finishes, reverse the collected levels to produce the bottom‑up ordering. Each node is processed once, so the time complexity remains O(n), while recursion depth and storage require O(n) space in the worst case for a skewed tree. This approach works well if you prefer recursive logic over queue-based iteration.
Recommended for interviews: The BFS queue approach is typically expected because it directly matches the definition of level order traversal in a binary tree. Using a stack (or reversing the result) to adjust the order shows you understand traversal mechanics. Recursive level construction demonstrates deeper control over tree traversal but is slightly less direct for this problem.
Approach 1: Approach 1: Level Order Traversal with Queue and Stack
This approach utilizes a queue to perform a standard level order traversal but stores each level of nodes in a separate list. After the traversal, the entire list of lists is reversed to provide the bottom-up level order.
In this Python solution, we use a double-ended queue (`deque`) from the `collections` module for the traversal. A queue allows us to efficiently perform level order traversal, adding child nodes to the queue and processing them in FIFO order. After processing all levels, we invert the result list to provide a bottom-up output.
Complexity
Time Complexity: O(n) where n is the number of nodes, as each node is processed once.
Space Complexity: O(n) for storing the queue and the result.
Approach 2: Approach 2: Recursive Level Order Traversal
This recursive approach traverses the tree, keeping track of the depth of each node. Nodes are added to sublists based on their depth, and the list of lists is reversed at the end to provide bottom-up level order.
In this JavaScript solution, a helper function `addToLevel` is used. It traverses the tree recursively. Each node's value is added to a sublist that corresponds to its depth, creating a level-wise list of nodes, which is then reversed to achieve the bottom-up order.
Code
JavaScript
C#
Complexity
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.
Approach 3: BFS
We can use the BFS (Breadth-First Search) method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:
- Traverse all nodes in the current queue, store their values in a temporary array
t, and then enqueue their child nodes. - Store the temporary array
tin the answer array.
Finally, return the reversed answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Level Order Traversal with Queue and Stack | Time Complexity: O(n) where n is the number of nodes, as each node is processed once. |
| Approach 2: Recursive Level Order Traversal | Time Complexity: O(n) where n is the number of nodes. |
| BFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Queue and Stack | O(n) | O(n) | Standard solution for level order problems. Best when using iterative BFS. |
| Recursive Level Order Traversal | O(n) | O(n) | Useful when you prefer DFS recursion or already track levels during traversal. |
Video Solution
Binary Tree Level Order Traversal ii | LeetCode 107 | C++, Java, Python • Knowledge Center • 10,924 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Level Order Traversal II easy or hard?
How to solve Binary Tree Level Order Traversal II in O(n)?
Binary Tree Level Order Traversal II Python or Java solution
What is the best approach for Binary Tree Level Order Traversal II?
What data structure is used in Binary Tree Level Order Traversal II?
What is the time complexity of Binary Tree Level Order Traversal II?
Is Binary Tree Level Order Traversal II asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Binary Tree Level Order Traversal II with our built-in code editor and test cases.
Practice on FleetCode