O(n) O(n)
Intuition
Do an ordinary breadth-first traversal, collecting one list per level. Bottom-up order is just the top-down level list reversed at the end.
Explanation
Level-order, then flip
Breadth-first search naturally visits the tree level by level. Process the queue in fixed-size batches — each batch is exactly one level — collecting that level's values, and enqueueing children for the next level.
if not root: return []
result = []; queue = [root]
while queue:
level = []
for _ in range(len(queue)): # snapshot this level's size
node = queue.pop_front()
level.append(node.val)
if node.left: queue.push(node.left)
if node.right: queue.push(node.right)
result.append(level)
return reversed(result)
The only difference from top-down level order is the final reverse.
Worked example
Tree [3,9,20,null,null,15,7]:
- Level 0:
[3] - Level 1:
[9, 20] - Level 2:
[15, 7]
Top-down is [[3],[9,20],[15,7]]; reversed (bottom-up) → [[15,7],[9,20],[3]].
Complexity
- Time: O(n).
- Space: O(n) for the queue and output.
Implementation
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
Collections.reverse(result);
return result;
}
}