LeetCode 1161 Solution: Maximum Level Sum of a Binary Tree

Problem Overview

In LeetCode 1161 (Maximum Level Sum of a Binary Tree), you’re given the root of a binary tree. Your task is to find which level (1-indexed) has the maximum sum of node values.

Important details

Levels are counted starting from 1 (root is level 1).
If multiple levels have the same maximum sum, you must return the smallest level number.
Node values can be negative, so don’t assume sums increase as you go deeper.

Key Insight

To compute the sum at each level, the most natural technique is:

✅ Level Order Traversal (BFS) — because BFS processes the tree level by level.

At each level:

Count how many nodes are in the queue (level_size)
Pop exactly that many nodes
Compute the sum of their values
Push their children into the queue
Track the best (maximum) sum and its level index

This also automatically handles the tie-break rule:

Only update the answer when you find a strictly greater sum.
If sums tie, you keep the earlier (smaller) level.

BFS Approach (Recommended)

Step-by-step Algorithm

If the tree is empty (not in LeetCode constraints usually), return 0 or handle accordingly.
Initialize:
- queue with the root
- level = 1
- max_sum = -infinity
- best_level = 1
While the queue is not empty:
- Compute current level_sum
- Compare with max_sum
- Update max_sum and best_level when level_sum > max_sum
- Increment level

Example Walkthrough

Consider the tree:

Level sums:

Level 1: 1
Level 2: 7 + 0 = 7
Level 3: 7 + (-8) = -1

Maximum sum is 7 at level 2, so the output is 2.

Python3 Solution (BFS)

from collections import deque
from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        level = 1

        max_sum = float("-inf")
        best_level = 1

        while q:
            level_size = len(q)
            level_sum = 0

            for _ in range(level_size):
                node = q.popleft()
                level_sum += node.val

                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            # Update only on strictly greater sum to keep smallest level on ties
            if level_sum > max_sum:
                max_sum = level_sum
                best_level = level

            level += 1

        return best_level

Java Solution (BFS)

import java.util.*;

class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int level = 1;
        int bestLevel = 1;
        long maxSum = Long.MIN_VALUE;

        while (!q.isEmpty()) {
            int size = q.size();
            long sum = 0;

            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sum += node.val;

                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }

            if (sum > maxSum) {
                maxSum = sum;
                bestLevel = level;
            }
            level++;
        }

        return bestLevel;
    }
}

C++ Solution (BFS)

#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        int level = 1, bestLevel = 1;
        long long maxSum = LLONG_MIN;

        while (!q.empty()) {
            int size = (int)q.size();
            long long sum = 0;

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                sum += node->val;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            if (sum > maxSum) {
                maxSum = sum;
                bestLevel = level;
            }
            level++;
        }

        return bestLevel;
    }
};

Complexity Analysis

Let n be the number of nodes in the tree.

Time Complexity: O(n)
Each node is visited exactly once.
Space Complexity: O(w)
Where w is the maximum width of the tree (worst-case can be O(n)).

Common Edge Cases to Remember

✅ All negative values: initialize max_sum to -infinity, not 0.
✅ Tie between levels: return the smallest level → update only when > not >=.
✅ Single node tree: answer is always 1.

Alternative Idea: DFS (When You Prefer Recursion)

Another valid solution is to do DFS and store sums in an array/list where index = level. After traversal, scan for the max sum. BFS is usually simpler and more direct for “per-level” problems, but DFS works well too.