Level-Order Accumulators, Compared

Four LeetCode problems, one algorithm. Each of them is 102's breadth-first traversal with the int sz = q.size() snapshot that separates the levels — and each one changes exactly two lines: what it does with a node's value, and what it does at the end of a level. Everything else on this page is identical from one problem to the next, which is the entire point of studying them together.

1 — The shared skeleton

Every visualizer below runs on the same tree and the same queue machinery:

Queue<TreeNode> q = new ArrayDeque<>();
if (root != null) q.add(root);
while (!q.isEmpty()) {
    int sz = q.size();                 // how many nodes are on THIS level
    for (int i = 0; i < sz; i++) {
        TreeNode nd = q.poll();
        // (1) accumulate nd.val somehow
        if (nd.left  != null) q.add(nd.left);
        if (nd.right != null) q.add(nd.right);
    }
    // (2) do something with the finished level
}

The snapshot on line 4 is load-bearing. Read q.size() inside the inner loop instead and it changes underneath you as children are appended, the level boundary dissolves, and all four problems below silently become the same flat traversal.

The tree, in all four cases:

2 — 107 · Level Order Traversal II

Accumulator: collect the level as a list, exactly like 102. Emit: addFirst instead of add.

That single word is the whole problem. Because LinkedList implements Deque, pushing each finished level onto the front produces bottom-up order in O(1) per level — no reversal pass, no second traversal, no recursion by depth. Declaring the result as LinkedList rather than List is what makes addFirst visible to the compiler; this is the one line people get wrong.

List<Integer> level = new ArrayList<>();while (!q.isEmpty()) {    int sz = q.size();          // snapshot    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        level.add(nd.val);        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    out.addFirst(level);}

Watch the answer strip grow leftward. The traversal itself never runs backwards — it is still strictly top-down — only the insertion point moves.

3 — 637 · Average of Levels

Accumulator: a running long sum. Emit: sum / (double) sz.

The trap here is arithmetic, not structure. Node values go up to 2³¹ − 1 and a level can hold thousands of them, so an int accumulator overflows on a wide level of large values — and it overflows silently, producing a plausible wrong average rather than an exception. Accumulate in long, then divide by sz cast to double.

List<Integer> level = new ArrayList<>();while (!q.isEmpty()) {    int sz = q.size();          // snapshot    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        sum += nd.val;        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    out.add(sum / (double) sz);}

Note that sz is the divisor, which is why the snapshot has to be taken before the inner loop starts consuming the queue.

4 — 515 · Largest Value in Each Row

Accumulator: a running max, seeded at Integer.MIN_VALUE. Emit: append that max.

The seed matters: values can be negative, so seeding at 0 returns 0 for any level whose values are all below zero. Seeding at Integer.MIN_VALUE is safe because every level in this problem is guaranteed non-empty — the outer while only runs when the queue has something in it, so the max is always replaced at least once.

List<Integer> level = new ArrayList<>();while (!q.isEmpty()) {    int sz = q.size();          // snapshot    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        best = Math.max(best, nd.val);        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    out.add(best);}

5 — 1161 · Maximum Level Sum

Accumulator: a running long sum. Emit: compare against the best so far and remember the level number.

This is 637 without the division, plus a counter — and the counter is the only real content. Levels are 1-indexed, and ties go to the smallest level number, so the comparison must be strictly greater (>, never >=) or a later level with an equal sum will steal the answer.

List<Integer> level = new ArrayList<>();while (!q.isEmpty()) {    int sz = q.size();          // snapshot    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        sum += nd.val;        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    if (sum > bestSum) { bestSum = sum; bestLvl = lvl; }}

In the example the level sums are 3, 29 and 22, so the answer is level 2. Had the increment been placed after the comparison, or the list been 0-indexed, the answer would come out as 1 — right sum, wrong label.

6 — Side by side

• Time: O(n) for all four — every node is enqueued once and polled once.
• Space: O(w) where w is the widest level, which is the queue's peak size. For 107 the output itself is an additional O(n).
• Empty tree: 107, 637 and 515 return an empty list; 1161 is guaranteed at least one node, but if you generalise it, decide explicitly what "no levels" should mean.
• DFS alternative: all four can be done with a depth-carrying DFS that indexes into a per-depth accumulator — see 199 for that shape. BFS is preferred here because the level boundary is explicit rather than inferred from an index.

7 — Reference implementations

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> out = new LinkedList<>();   // NOT List — addFirst must be visible
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>(sz);
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            level.add(nd.val);
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        out.addFirst(level);
    }
    return out;
}

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        long sum = 0;                          // long, or a wide level overflows
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            sum += nd.val;
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        out.add(sum / (double) sz);
    }
    return out;
}

public List<Integer> largestValues(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        int best = Integer.MIN_VALUE;            // not 0 — values can be negative
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            best = Math.max(best, nd.val);
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        out.add(best);
    }
    return out;
}

public int maxLevelSum(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    long bestSum = Long.MIN_VALUE;
    int bestLvl = 1, lvl = 0;
    while (!q.isEmpty()) {
        lvl++;                                 // 1-indexed, incremented BEFORE the compare
        int sz = q.size();
        long sum = 0;
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            sum += nd.val;
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        if (sum > bestSum) {                     // strictly > — ties keep the earlier level
            bestSum = sum;
            bestLvl = lvl;
        }
    }
    return bestLvl;
}

All four compile against the same TreeNode definition and differ only in the two marked lines. If you can write one of them cold, you can write the other three by editing those lines — which is exactly the check worth running before you move on.