1302 · Deepest Leaves Sum

Sum the values of the deepest leaves. The neat part is that you never have to find the depth first: run a level-order traversal and overwrite the running sum at every level, and whatever is left when the queue empties is the answer by construction.

1 — BFS: let the last level win

This is the level-order accumulator shape with an unusual emit step: instead of appending each level's result, throw the previous one away. The deepest level is simply the last one processed, so no separate depth pass is needed.

Queue<TreeNode> q = new ArrayDeque<>();q.add(root);int sum = 0;while (!q.isEmpty()) {    int sz = q.size();    sum = 0;                       // ASSIGN, not +=    for (int i = 0; i < sz; i++) { ... sum += nd.val; ... }}return sum;

The one character that matters is = rather than += on the reset line. Get that wrong and you compute the sum of the whole tree, which happens to be correct on a single-level tree — a pleasant way to pass the first sample and fail everything after it.

2 — DFS: bucket by depth

The recursive version needs one extra idea, because a DFS meets the deepest level partway through rather than at the end: track the deepest depth seen so far, and reset the sum whenever you go deeper than that.

void dfs(TreeNode nd, int d) {    if (nd == null) return;    if (d > best) { best = d; sum = 0; }    if (d == best) sum += nd.val;    dfs(nd.left,  d + 1);    dfs(nd.right, d + 1);}

Notice how the running total is discarded the first time depth 3 appears. The d > best and d == best pair does the same job as the BFS overwrite, just triggered by discovery order instead of by level boundaries.

3 — Complexity and edge cases

• Time: O(n) for both.
• Space: O(w) for BFS, where w is the widest level; O(h) for DFS. On a pathologically deep, narrow tree DFS is the one that risks a stack overflow; on a very wide tree BFS is the one that holds more.
• Single node: that node is itself the deepest leaf, so the answer is its value.
• Sum size: up to 10⁴ nodes with values to 100 keeps this inside int comfortably — unlike 637, where the constraints do force a long. Worth noticing that the two problems differ on exactly this point.
• "Deepest leaves" means every node at the maximum depth, not one of them, and not the leaves of the deepest subtree.

4 — Reference implementations

public int deepestLeavesSum(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    int sum = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        sum = 0;                            // assign — the last level survives
        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);
        }
    }
    return sum;
}

private int best = -1, sum = 0;

public int deepestLeavesSum(TreeNode root) {
    dfs(root, 0);
    return sum;
}

private void dfs(TreeNode nd, int d) {
    if (nd == null) return;
    if (d > best) { best = d; sum = 0; }   // found a deeper level — discard
    if (d == best) sum += nd.val;
    dfs(nd.left,  d + 1);
    dfs(nd.right, d + 1);
}