Maximum Level Sum of a Binary Tree

medium tree bfs

Problem

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on. Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Inputtree = [1, 7, 0, 7, -8, _, _]

Output2

Level 1: 1. Level 2: 7. Level 3: -1. Largest sum 7 at level 2.

tree (level-order)

def max_level_sum(root):
    if root is None: return 0
    level = [root]; depth = 1
    best = float('-inf'); best_depth = 1
    while level:
        s = sum(n.val for n in level)
        if s > best: best = s; best_depth = depth
        nxt = []
        for n in level:
            if n.left: nxt.append(n.left)
            if n.right: nxt.append(n.right)
        level = nxt; depth += 1
    return best_depth

function maxLevelSum(root) {
  if (!root) return 0;
  let level = [root], depth = 1, best = -Infinity, bestDepth = 1;
  while (level.length) {
    const sum = level.reduce((s, n) => s + n.val, 0);
    if (sum > best) { best = sum; bestDepth = depth; }
    const next = [];
    for (const n of level) { if (n.left) next.push(n.left); if (n.right) next.push(n.right); }
    level = next; depth++;
  }
  return bestDepth;
}

class Solution {
    public int maxLevelSum(TreeNode root) {
        if (root == null) return 0;
        List<TreeNode> level = new ArrayList<>(); level.add(root);
        int depth = 1, bestDepth = 1;
        long best = Long.MIN_VALUE;
        while (!level.isEmpty()) {
            long sum = 0; for (TreeNode n : level) sum += n.val;
            if (sum > best) { best = sum; bestDepth = depth; }
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode n : level) { if (n.left != null) next.add(n.left); if (n.right != null) next.add(n.right); }
            level = next; depth++;
        }
        return bestDepth;
    }
}

int maxLevelSum(TreeNode* root) {
    if (!root) return 0;
    vector<TreeNode*> level = { root };
    int depth = 1, bestDepth = 1;
    long long best = LLONG_MIN;
    while (!level.empty()) {
        long long sum = 0; for (auto* n : level) sum += n->val;
        if (sum > best) { best = sum; bestDepth = depth; }
        vector<TreeNode*> next;
        for (auto* n : level) { if (n->left) next.push_back(n->left); if (n->right) next.push_back(n->right); }
        level = next; depth++;
    }
    return bestDepth;
}

Explanation

The question is about whole levels of the tree, so the natural tool is breadth-first search (BFS), which processes the tree one level at a time.

We keep a list called level holding all the nodes at the current depth. We add up their values, and if that sum beats the best we have seen, we record it along with the current depth.

To advance, we build the next level by collecting every existing node's left and right children, then increment depth. The loop ends when a level has no nodes left.

Because we only overwrite bestDepth when a sum is strictly > the previous best, ties naturally keep the smallest level, exactly as the problem asks.

Example: [1, 7, 0, 7, -8, _, _]. Level sums are 1, then 7, then -1. The largest is 7 at level 2, so the answer is 2.

Time: O(n) Space: O(w)