Binary Tree Level Order Traversal II (LC 107)

Pattern: BFS — Level-by-Level Processing
Difficulty: Medium
Key Concept: Same level-order BFS as LC 102, then present levels from leaf to root (bottom-up)

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 level to root).

Input: TreeNode root — the root of a binary tree (may be null).
Output: List<List<Integer>> — each inner list is one level, ordered from the deepest level first up to the root level. Values within a level are still left-to-right.

Example (tree 3 → 9,20 → 15,7):

Top-down level order would be [[3], [9, 20], [15, 7]].
Bottom-up answer: [[15, 7], [9, 20], [3]].

1. Algorithm & Pseudocode

Idea: LC 102 builds levels from top to bottom. LC 107 is the same traversal; only the order of levels in the answer is reversed.

function levelOrderBottom(root):
    if root is null:
        return empty list

    result = empty list of lists
    queue = new queue containing root

    while queue is not empty:
        levelSize = queue.size()
        currentLevel = empty list

        repeat levelSize times:
            node = dequeue front
            append node.val to currentLevel
            if node.left exists: enqueue node.left
            if node.right exists: enqueue node.right

        append currentLevel to result   // still top-down order in result so far

    reverse result   // brute force: flip entire list of levels
    OR
    insert each currentLevel at index 0   // optimal with LinkedList: O(1) per level at front

    return result

Brute force: Build [[3], [9,20], [15,7]] then Collections.reverse(result).

Optimal twist: Use LinkedList<List<Integer>> and addFirst(currentLevel) so the final list is already bottom-up without a full reverse pass (same asymptotic time as BFS, slightly different constants).

2. Step-by-Step Analysis (Beginner-Friendly)

Why BFS? Level order means “all nodes at depth d before depth d+1.” A queue processes nodes in the order they are discovered, which matches level-by-level expansion.
Why track levelSize? Before you dequeue the first node of a level, queue.size() tells you how many nodes belong to this level. You must not mix the next level into the same inner list.
Why is this “just LC 102 reversed”? The definition of each level (left-to-right) is identical. Only whether you output shallow levels first or deep levels first changes.
Why not only use ArrayList and add(0, level)? ArrayList.add(0, x) shifts all elements — O(n) per insert where n is the size of the outer list. For L levels, repeated inserts at the front can become O(L²) in the worst case. LinkedList.addFirst() is O(1) for adding one level at the front.
Collections.reverse(result) after BFS is O(L) for L levels — simple and clear. Both “reverse at end” and “addFirst per level” are interview-acceptable; know the tradeoff.

3. The Dry Run

Tree (LeetCode array [3,9,20,null,null,15,7]):

BFS (same as LC 102): queue processes level by level; we show queue (front → back), currentLevel after the inner loop, and result after each outer iteration before reversing.

Step	Action	`levelSize`	`queue` (after processing level)	`currentLevel`	`result` (top-down, before reverse)
Init	`root` enqueued	—	`[3]`	—	`[]`
1	Process level 0	1	`[]` → enqueue `9`, `20` → `[9,20]`	`[3]`	`[[3]]`
2	Process level 1	2	`[15,7]`	`[9,20]`	`[[3],[9,20]]`
3	Process level 2	2	`[]`	`[15,7]`	`[[3],[9,20],[15,7]]`

After Collections.reverse(result): [[15,7],[9,20],[3]] ✓

Alternative trace (LinkedList + addFirst each level): after step 1 [[3]], after step 2 [[9,20],[3]], after step 3 [[15,7],[9,20],[3]] — already bottom-up.

4. Java Solution

Brute Force

Standard BFS (identical level building to LC 102), then reverse the outer list. Time: O(n) — each node visited once; reverse is O(number of levels). Space: O(w) queue width, worst O(n) on a complete last level.

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>(levelSize);

            for (int i = 0; i < levelSize; 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;
    }
}

Optimal

Same BFS, but accumulate with LinkedList.addFirst(0, level) so levels are stored bottom-up as you go. Time: O(n). Space: O(w) for the queue plus O(n) for the answer lists.

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>(levelSize);

            for (int i = 0; i < levelSize; 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.addFirst(level);
        }

        return result;
    }
}

(LeetCode provides TreeNode; same structure as other tree problems.)

5. The “Java vs. Others” Edge

LinkedList.addFirst(E e) (Java) adds at the head in O(1) — natural for “prepend each level.” In C++, std::deque or list::push_front plays the same role; vector::insert(begin(), ...) is O(n) like ArrayList.add(0, ...).
Collections.reverse(List<?>) is idiomatic when you already have an ArrayList of levels and want clarity over micro-optimizations.
Pitfall: Using new ArrayList<>() as the outer list and repeatedly add(0, level) causes O(L²) shifting — mention in interviews that you know why LinkedList or a single reverse is better.
This problem is a direct twist on LC 102; if you can explain 102, you only add “reverse order of levels.”

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	BFS O(n) + `Collections.reverse` O(levels); queue O(width)
Optimal	O(n)	O(n)	Same BFS; `addFirst` avoids separate reverse; still store all values

Here n is the number of nodes; space is dominated by the queue at the widest level and the output lists.