Maximum sum level of a binary tree

You're sitting across from a Microsoft interviewer who draws a binary tree on the whiteboard. Some nodes have large values, others have small or even negative ones. "Given this tree," they say, "which level has the highest total?" It sounds straightforward until you realize you need to process the tree level by level, keeping a running tally at each depth. This problem, also known as "Maximum Level Sum of a Binary Tree" on other platforms, tests your ability to combine breadth-first search with bookkeeping, and it's a favorite at companies like LinkedIn and Microsoft.

TL;DR

Use level-order traversal (BFS) with two queues to process nodes one level at a time. Sum each level's node values, compare against the running maximum, and track which level produced the highest sum. The algorithm runs in O(n) time since every node is visited once, and uses O(n) space for the queues. The two-queue technique makes level boundaries explicit: when the current queue empties, you know the level is done and can compare sums before swapping queues.

Why This Problem Matters

This problem sits at the intersection of two core interview topics: binary trees and BFS. It goes beyond simple traversal by requiring you to aggregate data at each level and track a global maximum across levels. Interviewers love it because it reveals whether you can extend a standard BFS template to solve a slightly more complex task. Once you have this pattern down, problems like "average of levels," "largest value in each row," and "zigzag level order traversal" all become variations on the same theme.

Binary Trees and Level-Order Traversal

A binary tree organizes data hierarchically. Each node holds a value and points to at most two children. Level-order traversal visits nodes top to bottom, left to right, processing all nodes at one depth before moving to the next.

In the tree above, level 0 contains just the root (value 1), level 1 has nodes 7 and 3, and level 2 has nodes 4 and 5. The sums are 1, 10, and 9 respectively. Level 1 wins with a sum of 10, so the answer is 1.

Understanding the Problem

Given: The root node of a binary tree Find: The 0-indexed level with the maximum sum of node values Return: The index of that level

Here is the example from the problem statement:

tree: 1 7 3 # # 4 5

      1
     / \
    7   3
       / \
      4   5

maxSumLevel(root) -> 1

Level 1 (containing 7 and 3) has the largest sum of 10.

Edge Cases to Consider

1. Single node: Only one level exists, so the answer is always 0.
2. Skewed tree: Every level has exactly one node. The level with the largest individual value wins.
3. Negative values: Nodes can have negative data. Initializing maxSum to Integer.MIN_VALUE handles this correctly.
4. Tied levels: If two levels share the same sum, we return the first (lowest index) one.

Solution Approach

The key observation is that we need to process the tree level by level. This immediately points to BFS rather than DFS. But standard BFS with a single queue doesn't tell you when one level ends and the next begins.

The Two-Queue Technique

The solution uses two queues to establish clear level boundaries:

1. curLevelQueue holds nodes at the current level being processed.
2. nextLevelQueue collects children of current-level nodes.

When curLevelQueue is empty, you've finished the current level. Compare its sum against the running max, then swap the queues: curLevelQueue takes over nextLevelQueue's contents, and nextLevelQueue starts fresh.

Here is how the queues evolve for our example tree:

The highlighted "Swap" steps mark level transitions. At each swap, we compare the level sum against maxSum and update if we found a new maximum.

Building the Algorithm

Let's trace through the full algorithm with the example tree 1 7 3 # # 4 5:

Initialization:

• curLevelQueue = [1], nextLevelQueue = []
• currentSum = 0, maxSum = -infinity, maxSumLevelIndex = 0, currentLevelIndex = 0

Level 0:

• Dequeue node 1. currentSum = 1. Enqueue children 7 and 3 to nextLevelQueue.
• curLevelQueue is empty. Compare: 1 > -infinity, so maxSum = 1, maxSumLevelIndex = 0.
• Swap queues. curLevelQueue = [7, 3], nextLevelQueue = []. Increment level to 1.

Level 1:

• Dequeue node 7. currentSum = 7. No children for 7.
• Dequeue node 3. currentSum = 10. Enqueue 4 and 5 to nextLevelQueue.
• curLevelQueue is empty. Compare: 10 > 1, so maxSum = 10, maxSumLevelIndex = 1.
• Swap queues. Increment level to 2.

Level 2:

• Dequeue node 4. currentSum = 4. No children.
• Dequeue node 5. currentSum = 9. No children.
• curLevelQueue is empty. Compare: 9 < 10. No update.
• Swap queues. curLevelQueue is now empty, so the while loop exits.

Result: maxSumLevelIndex = 1.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int maxSumLevel(TreeNode root) {
    int currentLevelIndex = 0, currentSum = 0;
    int maxSumLevelIndex = 0, maxSum = Integer.MIN_VALUE;
    Deque<TreeNode> curLevelQueue = new LinkedList<>(), nextLevelQueue = new LinkedList<>();

    curLevelQueue.offer(root);

    while (!curLevelQueue.isEmpty()) {
      TreeNode node = curLevelQueue.poll();
      currentSum += node.data;

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

      if (curLevelQueue.isEmpty()) {
        if (maxSum < currentSum) {
          maxSum = currentSum;
          maxSumLevelIndex = currentLevelIndex;
        }
        currentSum = 0;
        currentLevelIndex += 1;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = new LinkedList<>();
      }
    }

    return maxSumLevelIndex;
  }
}

The outer while loop runs until there are no more nodes to process. Inside, we dequeue one node at a time, add its value to currentSum, and enqueue its children to nextLevelQueue. When curLevelQueue empties, a level transition happens: we compare sums, reset counters, and swap queues.

Walkthrough with Traversal Animation

The animation shows how each node gets visited in BFS order. After processing all nodes at a level, the algorithm compares the level sum against the running maximum.

Complexity Analysis

Time Complexity: O(n)

Each of the n nodes is enqueued and dequeued exactly once. Per-node work (adding to sum, enqueuing children, comparison at level boundary) is O(1). The total is O(n).

Space Complexity: O(n)

The queues hold at most all nodes at two adjacent levels. In a complete binary tree, the widest level has roughly n/2 nodes. The additional tracking variables use O(1) space. Overall: O(n).

For a fully balanced tree, this is the worst case. A skewed tree (each level has one node) would use O(1) queue space, but the algorithm is still O(n) time because it visits every node.

In the balanced tree above, level 2 holds four nodes (4, 5, 6, 7) with sum 22. That is the widest level, and all four nodes would sit in the queue at the same time.

Alternative Approaches

1. Single queue with size counter: Record queue.size() at each level start, dequeue exactly that many nodes. Same complexity, slightly different structure.
2. DFS with depth map: Recurse through the tree, accumulating sums in a HashMap<Integer, Integer> keyed by depth. After traversal, scan the map for the max. Also O(n) time and space, but less natural for a level-centric problem.
3. Recursive BFS simulation: Pass the entire level's worth of nodes into a recursive call. Elegant but hard to read in interviews.

The two-queue approach is the clearest for interviews because the level boundaries are visually obvious in the code.

Common Pitfalls

1. Initializing maxSum to 0: This fails when all node values are negative. Use Integer.MIN_VALUE (or the language equivalent) instead.

2. Forgetting to reset currentSum: After comparing at the level boundary, you must reset currentSum to 0 before processing the next level. Forgetting this causes sums to accumulate across levels.

3. Off-by-one on level index: The levels are 0-indexed. Make sure you increment currentLevelIndex after comparing, not before.

4. Using <= instead of < for the comparison: Using <= would return the last level with the max sum. The problem expects the first, so use strict <.

Interview Tips

When solving this problem in an interview:

1. Clarify the problem: "Are levels 0-indexed?" "What should I return if multiple levels tie?" "Can node values be negative?"

2. Sketch the tree: Draw the example and label each level's sum. This makes the two-queue approach feel natural when you explain it.

3. Explain the two-queue trick: "I'll use two queues to separate levels. When the current queue empties, I know the level is done." This demonstrates strong BFS understanding.

4. Watch for follow-ups:

   • "What if I want the level with the minimum sum?" (Change < to >, init to Integer.MAX_VALUE)
   • "Return all level sums." (Store sums in a list instead of tracking max)
   • "What about an n-ary tree?" (Enqueue all children, same algorithm)

5. Mention the single-queue alternative: Showing you know multiple approaches to level-order traversal signals depth of knowledge.

Key Takeaways

• The two-queue BFS pattern processes binary tree levels independently, making it ideal for any "per-level" aggregation problem.
• Initialize maxSum to Integer.MIN_VALUE, not 0, to handle trees with all-negative values correctly.
• The algorithm visits each node once (O(n) time) and holds at most one level's worth of nodes in the queues (O(n) space in the worst case for a wide tree).
• This pattern transfers directly to related problems: level averages, largest value per row, zigzag traversal, and bottom-up level order.
• At the level boundary (when curLevelQueue empties), compare, reset, and swap. Getting this transition right is what separates a working solution from a buggy one.

Practice and Related Problems

Once you're comfortable with this problem, try these related challenges to solidify your BFS and level-order skills:

• Level order traversal (basic BFS without aggregation)
• Bottom-up level order traversal (reverse the result)
• Binary tree right side view (last node at each level)
• Average of levels in a binary tree (divide sum by count)

This problem and many others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you're just getting started with trees or polishing your BFS toolkit, consistent practice on problems like this one will build the pattern recognition that makes interview day feel routine.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def max_sum_level(self, root):
        current_level_index, current_sum = 0, 0
        max_sum_level_index, max_sum = 0, float('-inf')
        cur_level_queue, next_level_queue = deque(), deque()
        cur_level_queue.append(root)

        while len(cur_level_queue) > 0:
            node = cur_level_queue.popleft()
            current_sum += node.data
            if node.left is not None:
                next_level_queue.append(node.left)
            if node.right is not None:
                next_level_queue.append(node.right)
            if len(cur_level_queue) == 0:
                if max_sum < current_sum:
                    max_sum = current_sum
                    max_sum_level_index = current_level_index
                current_sum = 0
                current_level_index += 1
                cur_level_queue = next_level_queue
                next_level_queue = deque()

        return max_sum_level_index

JavaScript

class Solution {
  maxSumLevel(root) {
    let currentLevelIndex = 0, currentSum = 0;
    let maxSumLevelIndex = 0, maxSum = Number.NEGATIVE_INFINITY;
    let curLevelQueue = [root], nextLevelQueue = [];

    while (curLevelQueue.length > 0) {
      const node = curLevelQueue.shift();
      currentSum += node.data;
      if (node.left !== null) nextLevelQueue.push(node.left);
      if (node.right !== null) nextLevelQueue.push(node.right);
      if (curLevelQueue.length === 0) {
        if (maxSum < currentSum) {
          maxSum = currentSum;
          maxSumLevelIndex = currentLevelIndex;
        }
        currentSum = 0;
        currentLevelIndex += 1;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = [];
      }
    }

    return maxSumLevelIndex;
  }
}

TypeScript

class Solution {
  maxSumLevel(root: TreeNode): number {
    let currentLevelIndex = 0, currentSum = 0;
    let maxSumLevelIndex = 0, maxSum = Number.NEGATIVE_INFINITY;
    let curLevelQueue: TreeNode[] = [root], nextLevelQueue: TreeNode[] = [];

    while (curLevelQueue.length > 0) {
      const node = curLevelQueue.shift()!;
      currentSum += node.data;
      if (node.left !== null) nextLevelQueue.push(node.left);
      if (node.right !== null) nextLevelQueue.push(node.right);
      if (curLevelQueue.length === 0) {
        if (maxSum < currentSum) {
          maxSum = currentSum;
          maxSumLevelIndex = currentLevelIndex;
        }
        currentSum = 0;
        currentLevelIndex += 1;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = [];
      }
    }

    return maxSumLevelIndex;
  }
}

C++

#include <queue>
#include <climits>

class Solution {
public:
  int maxSumLevel(TreeNode *root) {
    int currentLevelIndex = 0, currentSum = 0;
    int maxSumLevelIndex = 0, maxSum = INT_MIN;
    std::queue<TreeNode *> curLevelQueue, nextLevelQueue;
    curLevelQueue.push(root);

    while (!curLevelQueue.empty()) {
      TreeNode *node = curLevelQueue.front();
      curLevelQueue.pop();
      currentSum += node->data;
      if (node->left != nullptr) nextLevelQueue.push(node->left);
      if (node->right != nullptr) nextLevelQueue.push(node->right);
      if (curLevelQueue.empty()) {
        if (maxSum < currentSum) {
          maxSum = currentSum;
          maxSumLevelIndex = currentLevelIndex;
        }
        currentSum = 0;
        currentLevelIndex += 1;
        curLevelQueue = std::queue<TreeNode *>(nextLevelQueue);
        nextLevelQueue = std::queue<TreeNode *>();
      }
    }

    return maxSumLevelIndex;
  }
};

Scala

import scala.collection.mutable

class Solution {
  def maxSumLevel(root: TreeNode): Int = {
    var currentLevelIndex = 0
    var currentSum = 0
    var maxSumLevelIndex = 0
    var maxSum = Int.MinValue
    var curLevelQueue = mutable.Queue[TreeNode]()
    var nextLevelQueue = mutable.Queue[TreeNode]()
    curLevelQueue.enqueue(root)

    while (curLevelQueue.nonEmpty) {
      val node = curLevelQueue.dequeue
      currentSum += node.data
      if (node.left != null) nextLevelQueue.enqueue(node.left)
      if (node.right != null) nextLevelQueue.enqueue(node.right)
      if (curLevelQueue.isEmpty) {
        if (maxSum < currentSum) {
          maxSum = currentSum
          maxSumLevelIndex = currentLevelIndex
        }
        currentSum = 0
        currentLevelIndex += 1
        curLevelQueue = nextLevelQueue
        nextLevelQueue = mutable.Queue[TreeNode]()
      }
    }

    maxSumLevelIndex
  }
}

Kotlin

import java.util.ArrayDeque

class Solution {
    fun maxSumLevel(root: TreeNode): Int {
        var currentLevelIndex = 0
        var currentSum = 0
        var maxSumLevelIndex = 0
        var maxSum = Int.MIN_VALUE
        var curLevelQueue = ArrayDeque<TreeNode>()
        var nextLevelQueue = ArrayDeque<TreeNode>()
        curLevelQueue.add(root)

        while (curLevelQueue.isNotEmpty()) {
            val node = curLevelQueue.removeFirst()
            currentSum += node.data
            node.left?.let { nextLevelQueue.add(it) }
            node.right?.let { nextLevelQueue.add(it) }
            if (curLevelQueue.isEmpty()) {
                if (maxSum < currentSum) {
                    maxSum = currentSum
                    maxSumLevelIndex = currentLevelIndex
                }
                currentSum = 0
                currentLevelIndex += 1
                curLevelQueue = nextLevelQueue
                nextLevelQueue = ArrayDeque()
            }
        }

        return maxSumLevelIndex
    }
}

Swift

class Solution {
    func maxSumLevel(_ root: TreeNode?) -> Int {
        var currentLevelIndex = 0
        var currentSum = 0
        var maxSumLevelIndex = 0
        var maxSum = Int.min
        var curLevelQueue: [TreeNode] = []
        var nextLevelQueue: [TreeNode] = []

        if let root = root {
            curLevelQueue.append(root)
        }

        while !curLevelQueue.isEmpty {
            let node = curLevelQueue.removeFirst()
            currentSum += node.data
            if let left = node.left { nextLevelQueue.append(left) }
            if let right = node.right { nextLevelQueue.append(right) }
            if curLevelQueue.isEmpty {
                if maxSum < currentSum {
                    maxSum = currentSum
                    maxSumLevelIndex = currentLevelIndex
                }
                currentSum = 0
                currentLevelIndex += 1
                curLevelQueue = nextLevelQueue
                nextLevelQueue = []
            }
        }

        return maxSumLevelIndex
    }
}

Ruby

class Solution
  def max_sum_level(root)
    current_level_index = 0
    current_sum = 0
    max_sum_level_index = 0
    max_sum = -Float::INFINITY
    cur_level_queue = []
    next_level_queue = []
    cur_level_queue.push(root)

    until cur_level_queue.empty?
      node = cur_level_queue.shift
      current_sum += node.data
      next_level_queue.push(node.left) if node.left
      next_level_queue.push(node.right) if node.right
      if cur_level_queue.empty?
        if max_sum < current_sum
          max_sum = current_sum
          max_sum_level_index = current_level_index
        end
        current_sum = 0
        current_level_index += 1
        cur_level_queue = next_level_queue
        next_level_queue = []
      end
    end

    max_sum_level_index
  end
end

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn max_sum_level(&self, root: Option<Box<TreeNode>>) -> i32 {
        let mut current_level_index = 0;
        let mut current_sum = 0;
        let mut max_sum_level_index = 0;
        let mut max_sum = i32::MIN;
        let mut cur_level_queue: VecDeque<&TreeNode> = VecDeque::new();
        let mut next_level_queue: VecDeque<&TreeNode> = VecDeque::new();
        cur_level_queue.push_back(root.as_deref().unwrap());

        while !cur_level_queue.is_empty() {
            let node = cur_level_queue.pop_front().unwrap();
            current_sum += node.data;
            if let Some(ref left) = node.left {
                next_level_queue.push_back(left);
            }
            if let Some(ref right) = node.right {
                next_level_queue.push_back(right);
            }
            if cur_level_queue.is_empty() {
                if max_sum < current_sum {
                    max_sum = current_sum;
                    max_sum_level_index = current_level_index;
                }
                current_sum = 0;
                current_level_index += 1;
                cur_level_queue = next_level_queue;
                next_level_queue = VecDeque::new();
            }
        }

        max_sum_level_index
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public int MaxSumLevel(TreeNode root) {
        int currentLevelIndex = 0, currentSum = 0;
        int maxSumLevelIndex = 0, maxSum = int.MinValue;
        var curLevelQueue = new Queue<TreeNode>();
        var nextLevelQueue = new Queue<TreeNode>();
        curLevelQueue.Enqueue(root);

        while (curLevelQueue.Count > 0) {
            var node = curLevelQueue.Dequeue();
            currentSum += node.data;
            if (node.left != null) nextLevelQueue.Enqueue(node.left);
            if (node.right != null) nextLevelQueue.Enqueue(node.right);
            if (curLevelQueue.Count == 0) {
                if (maxSum < currentSum) {
                    maxSum = currentSum;
                    maxSumLevelIndex = currentLevelIndex;
                }
                currentSum = 0;
                currentLevelIndex += 1;
                curLevelQueue = nextLevelQueue;
                nextLevelQueue = new Queue<TreeNode>();
            }
        }

        return maxSumLevelIndex;
    }
}

Dart

import 'dart:collection';

class Solution {
  int maxSumLevel(TreeNode? root) {
    int currentLevelIndex = 0, currentSum = 0;
    int maxSumLevelIndex = 0, maxSum = -1 << 31;
    Queue<TreeNode> curLevelQueue = Queue();
    Queue<TreeNode> nextLevelQueue = Queue();
    curLevelQueue.add(root!);

    while (curLevelQueue.isNotEmpty) {
      TreeNode node = curLevelQueue.removeFirst();
      currentSum += node.data;
      if (node.left != null) nextLevelQueue.add(node.left!);
      if (node.right != null) nextLevelQueue.add(node.right!);
      if (curLevelQueue.isEmpty) {
        if (maxSum < currentSum) {
          maxSum = currentSum;
          maxSumLevelIndex = currentLevelIndex;
        }
        currentSum = 0;
        currentLevelIndex += 1;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = Queue();
      }
    }

    return maxSumLevelIndex;
  }
}

PHP

class Solution {
    public function maxSumLevel(?TreeNode $root): int {
        $currentLevelIndex = 0;
        $currentSum = 0;
        $maxSumLevelIndex = 0;
        $maxSum = PHP_INT_MIN;
        $curLevelQueue = [$root];
        $nextLevelQueue = [];

        while (!empty($curLevelQueue)) {
            $node = array_shift($curLevelQueue);
            $currentSum += $node->data;
            if ($node->left !== null) $nextLevelQueue[] = $node->left;
            if ($node->right !== null) $nextLevelQueue[] = $node->right;
            if (empty($curLevelQueue)) {
                if ($maxSum < $currentSum) {
                    $maxSum = $currentSum;
                    $maxSumLevelIndex = $currentLevelIndex;
                }
                $currentSum = 0;
                $currentLevelIndex += 1;
                $curLevelQueue = $nextLevelQueue;
                $nextLevelQueue = [];
            }
        }

        return $maxSumLevelIndex;
    }
}