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 from the root downward, you collect levels normally and return them in reverse order.
Approach 1: Level Order Traversal with Queue and Stack (O(n) time, O(n) space)
This approach uses classic Breadth-First Search on a binary tree. Push the root into a queue, then process nodes level by level. For each level, iterate through the queue size, collect node values, and enqueue their left and right children. Instead of appending each level directly to the result, push it onto a stack (or prepend to the result). After the traversal finishes, pop levels from the stack to produce the bottom-up order.
The key insight: BFS already groups nodes by depth. Reversing the order of those groups gives the required output without modifying the traversal logic. Each node is visited exactly once, giving O(n) time complexity. The queue and stack together require O(n) space in the worst case.
Approach 2: Recursive Level Order Traversal (O(n) time, O(n) space)
This method performs a depth-first traversal while tracking the current level index. During recursion, create a list for a level when you encounter it for the first time. Append the node value to the list corresponding to its depth. Continue recursively for the left and right children with level + 1. Once the traversal finishes, reverse the list of levels to produce the bottom-up order.
The insight here is that recursion naturally explores the tree structure while maintaining depth information. Instead of grouping nodes during BFS, you group them using their depth index. This approach is concise and easy to implement in languages where recursion is idiomatic. Time complexity remains O(n) since every node is processed once, and the recursion stack plus result storage uses up to O(n) space.
Recommended for interviews: The queue-based BFS solution is what interviewers typically expect. It demonstrates clear understanding of level-order traversal and queue mechanics. The recursive solution is also valid and elegant, but BFS shows stronger familiarity with tree traversal patterns commonly used in production and interview settings.
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.
Java
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.
C#
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Queue and Stack | O(n) | O(n) | Standard BFS solution for tree level traversal; most common interview approach |
| Recursive Level Tracking (DFS) | O(n) | O(n) | When recursion is preferred or when implementing DFS-based tree traversals |
Binary Tree Level Order Traversal - BFS - Leetcode 102 • NeetCode • 220,937 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 FleetCodePractice this problem
Open in Editor