Tree Level With the Largest Sum

medium tree bfs

Problem

Return the smallest 1-indexed level whose sum of node values is the largest in the tree. BFS level by level, summing as you go and tracking the current best.

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;
}

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