Maximum Level Sum of a Binary Tree

Medium
1942.

Maximum Level Sum of a Binary Tree

Maximum Level Sum of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, number its levels from the top: the root is on level 1, its children on level 2, and so on.

Return the level whose node values add up to the largest sum. If several levels share that largest sum, return the smallest such level.

Example 1

Input
root = [1,7,0,7,-8]
Output
2
Explanation
The level sums are 1, 7 + 0 = 7 and 7 - 8 = -1; level 2 is the largest.

Example 2

Input
root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output
2
Explanation
The sums are 989, 10250, 98693 - 89388 = 9305 and -32127; level 2 wins.

Example 3

Input
root = [1,2,-1]
Output
1
Explanation
Levels 1 and 2 both sum to 1; the smaller level number, 1, is returned.

Constraints

  • 1 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Level Sum of a Binary Tree — Problem & Solution

Maximum Level Sum of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Level Sum of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, number its levels from the top: the root is on level 1, its children on level 2, and so on.

Return the level whose node values add up to the largest sum. If several levels share that largest sum, return the smallest such level.

Example 1

Input: root = [1,7,0,7,-8]
Output: 2
Explanation: The level sums are 1, 7 + 0 = 7 and 7 - 8 = -1; level 2 is the largest.

Example 2

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2
Explanation: The sums are 989, 10250, 98693 - 89388 = 9305 and -32127; level 2 wins.

Example 3

Input: root = [1,2,-1]
Output: 1
Explanation: Levels 1 and 2 both sum to 1; the smaller level number, 1, is returned.

Constraints

  • 1 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5

Hints for Maximum Level Sum of a Binary Tree

  1. Hint 1

    You need one number per level, so visit the tree level by level.

  2. Hint 2

    A breadth-first walk that processes exactly the nodes currently in the queue at a time handles one whole level per round.

  3. Hint 3

    Keep the best sum and its level; replace them only on a strictly larger sum so ties keep the earlier level. Sums can be negative — do not start the best at 0.

How to solve Maximum Level Sum of a Binary Tree

A breadth-first walk visits the tree one level at a time; sum each level and keep the first level that reaches the maximum.

Approach

  1. Put the root in a queue and set the level counter to 0.
  2. While the queue is not empty: increase the level, take exactly the nodes now in the queue, add up their values and enqueue their children.
  3. If this is the first level or its sum is strictly larger than the best so far, record the sum and the level.
  4. Return the recorded level.

Why it works

Each round of the walk removes exactly the nodes of one level, because those are precisely the nodes enqueued during the previous round. Comparing with a strict > keeps the earliest level among equal sums.

Complexity

  • Time — O(n)
  • Space — O(w), w the widest level

Pitfalls

  • Initialising the best sum to 0 fails when every level sum is negative.
  • Using >= returns the last level among ties instead of the first.

Reference solution

Python

from typing import Optional

def maxLevelSum(root: Optional[TreeNode]) -> int:
    best_sum = None
    best_level = 1
    level = [root]
    depth = 0
    while level:
        depth += 1
        total = 0
        nxt = []
        for node in level:
            total += node.val
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        if best_sum is None or total > best_sum:
            best_sum = total
            best_level = depth
        level = nxt
    return best_level

Java

public static int maxLevelSum(TreeNode root) {
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    int depth = 0, bestLevel = 1;
    long bestSum = Long.MIN_VALUE;
    while (!queue.isEmpty()) {
        depth++;
        long total = 0;
        for (int i = queue.size(); i > 0; i--) {
            TreeNode node = queue.poll();
            total += node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        if (total > bestSum) { bestSum = total; bestLevel = depth; }
    }
    return bestLevel;
}

C++

int maxLevelSum(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0, bestLevel = 1;
    long long bestSum = LLONG_MIN;
    while (!q.empty()) {
        depth++;
        long long total = 0;
        for (int i = (int) q.size(); i > 0; i--) {
            TreeNode* node = q.front();
            q.pop();
            total += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        if (total > bestSum) { bestSum = total; bestLevel = depth; }
    }
    return bestLevel;
}

JavaScript

var maxLevelSum = function(root) {
    var queue = [root], head = 0, depth = 0, bestLevel = 1, bestSum = 0;
    while (head < queue.length) {
        var end = queue.length, total = 0;
        depth++;
        while (head < end) {
            var node = queue[head++];
            total += node.val;
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        if (depth === 1 || total > bestSum) { bestSum = total; bestLevel = depth; }
    }
    return bestLevel;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals