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:
[0, 2000].-1000 <= Node.val <= 1000Problem 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.
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.
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.
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.
JavaScript
C#
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.
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:
t, and then enqueue their child nodes.t in 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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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 | — |
| 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. |
Binary Tree Level Order Traversal ii | LeetCode 107 | C++, Java, Python • Knowledge Center • 10,837 views views
Watch 9 more video solutions →Practice Binary Tree Level Order Traversal II with our built-in code editor and test cases.
Practice on FleetCode