Maximum Level Sum of a Binary Tree solution and explanation
Google
9 more videos on this problem
Maximum Level Sum of a Binary Tree | Leetcode 1161 | AMAZON | codestorywithMIKcodestorywithMIK · 20:01 · 11K views
1161. Maximum Level Sum of a Binary Tree | Leetcode Daily - PythonLeetcode Daily · 9:36 · 1K views
Leetcode Solution - 1161 Maximum Level Sum of a Binary TreeJohn Leonardo · 4:30 · 811 views
1161. Maximum Level Sum of a Binary Tree (Leetcode Medium)Programming Live with Larry · 4:53 · 577 views
Maximum Level Sum of a Binary Tree - LeetCode 1161 - PythonAlpha-Code · 17:55 · 487 views
1161. Maximum Level Sum of a Binary Tree - English VersionSimple Code - 단순코드 · 6:52 · 208 views
Maximum Level Sum of a Binary Tree - Leetcode 1161 - PythonTim Huang · 4:54 · 205 views
Maximum Level Sum of a Binary Tree | Leetcode 1161 | How to solve Binary Tree Interview QuestionsCodeMap · 4:29 · 184 views
Leetcode | 1161 Maximum Level Sum of a Binary Tree | Java | Binary Tree | Daily ChallengeCakot Coding · 9:56 · 179 views
1161. Maximum Level Sum of a Binary Tree LeetCode | Binary Search TreeThe Stylish Coder · 12:08 · 173 views
The 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.
Example 1:
Input: root = [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.
Example 2:
Input: root = [989,null,10250,98693,-89388,null,null,null,-32127] Output: 2
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105
Approach overview
Problem Overview: You’re given the root of a binary tree. Each level contains several nodes, and each node has an integer value. The task is to compute the sum of values at every level and return the level index (1-indexed) that has the maximum sum.
The key observation: nodes on the same depth belong to the same level. If you process the tree level by level, you can compute the sum for each level and track the maximum as you go.
Approach 1: Breadth-First Search (Level Order Traversal) (Time: O(n), Space: O(w))
This approach uses Breadth-First Search to traverse the binary tree level by level. Start by pushing the root node into a queue. For each iteration, process all nodes currently in the queue (which represent one level). Sum their values, enqueue their left and right children, and compare the level sum with the current maximum.
The queue naturally separates nodes by level because children are added only after their parent level is processed. Maintain variables for currentLevel, maxSum, and resultLevel. Whenever a level sum exceeds maxSum, update the answer. This approach is straightforward and matches how most interviewers expect you to handle level-based tree problems.
Time complexity is O(n) since each node is processed exactly once. Space complexity is O(w), where w is the maximum width of the tree, due to the queue storing nodes of the current level.
Approach 2: Depth-First Search with Level Tracking (Time: O(n), Space: O(h))
A recursive solution using Depth-First Search also works. Instead of processing by levels explicitly, DFS tracks the current depth while traversing the tree. Maintain a dynamic array where index i stores the cumulative sum for level i. During recursion, add the node’s value to the corresponding level entry.
If the DFS reaches a depth that hasn’t been seen before, append a new element to the array. After the traversal completes, scan the array to find the level with the maximum sum. This approach separates traversal from result evaluation and works well in recursive implementations.
Time complexity remains O(n) because every node is visited once. Space complexity is O(h) for recursion stack depth (where h is tree height) plus O(L) for storing level sums.
Recommended for interviews: The BFS level-order traversal is typically the expected solution. The problem explicitly revolves around levels, so using a queue to process nodes level by level demonstrates a clear understanding of tree traversal patterns. The DFS approach is still valid and shows flexibility, but BFS is usually the first method interviewers want to see.
Approach 1: Breadth-First Search (BFS) Approach
The BFS approach is well-suited for problems involving levels of a binary tree. We will use a queue to process the tree level by level, keeping track of the sum of node values at each level. We will maintain a variable to store the maximum sum encountered and the level corresponding to this maximum sum. By processing level by level, we ensure that when we find a new maximum, it is the smallest level with that sum.
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxLevelSum(self, root: TreeNode) -> int:
if not root:
return 0
q = deque([root])
max_sum = float('-inf')
level = 0
max_level = 0
while q:
level_sum = 0
level += 1
for _ in range(len(q)):
node = q.popleft()
level_sum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if level_sum > max_sum:
max_sum = level_sum
max_level = level
return max_level
# Example Usage
root = TreeNode(1)
root.left = TreeNode(7)
root.right = TreeNode(0)
root.left.left = TreeNode(7)
root.left.right = TreeNode(-8)
sol = Solution()
print(sol.maxLevelSum(root))import java.util.LinkedList;
import java.util.Queue;
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class MaximumLevelSum {
public int maxLevelSum(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int maxSum = Integer.MIN_VALUE;
int level = 0;
int maxLevel = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
int levelSum = 0;
level++;
for (int i = 0; i < levelSize; ++i) {
TreeNode node = queue.poll();
levelSum += node.val;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = level;
}
}
return maxLevel;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(7);
root.right = new TreeNode(0);
root.left.left = new TreeNode(7);
root.left.right = new TreeNode(-8);
MaximumLevelSum solution = new MaximumLevelSum();
System.out.println("Max Level Sum: " + solution.maxLevelSum(root));
}
}#include <iostream>
#include <queue>
#include <limits.h>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int maxLevelSum(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int maxSum = INT_MIN, level = 0, maxLevel = 0;
while (!q.empty()) {
int levelSize = q.size();
int levelSum = 0;
level++;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
levelSum += node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = level;
}
}
return maxLevel;
}
int main() {
// Example Usage
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(7);
root->right = new TreeNode(0);
root->left->left = new TreeNode(7);
root->left->right = new TreeNode(-8);
cout << "Max Level Sum: " << maxLevelSum(root) << endl;
return 0;
}// Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function maxLevelSum(root) {
if (!root) return 0;
let queue = [root];
let maxSum = -Infinity;
let level = 0;
let maxLevel = 0;
while (queue.length > 0) {
let levelSize = queue.length;
let levelSum = 0;
level++;
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
levelSum += node.val;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = level;
}
}
return maxLevel;
}
// Example Usage
let root = new TreeNode(1);
root.left = new TreeNode(7);
root.right = new TreeNode(0);
root.left.left = new TreeNode(7);
root.left.right = new TreeNode(-8);
console.log(maxLevelSum(root));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// Queue Node
typedef struct QueueNode {
struct TreeNode* treeNode;
struct QueueNode* next;
} QueueNode;
// Queue
typedef struct {
QueueNode *front, *rear;
} Queue;
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(Queue* q, struct TreeNode *node) {
QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
temp->treeNode = node;
temp->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct TreeNode* deQueue(Queue* q) {
if (q->front == NULL)
return NULL;
QueueNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
struct TreeNode* node = temp->treeNode;
free(temp);
return node;
}
int maxLevelSum(struct TreeNode* root) {
if (!root) return 0;
Queue* q = createQueue();
enQueue(q, root);
int maxSum = INT_MIN, level = 0, maxLevel = 0;
while (1) {
int levelSize = 0, levelSum = 0;
QueueNode* temp = q->front;
// Calculate the size of the current level
while (temp) {
levelSize++;
temp = temp->next;
}
if (levelSize == 0) break;
level++;
while (levelSize--) {
struct TreeNode* node = deQueue(q);
levelSum += node->val;
if (node->left) enQueue(q, node->left);
if (node->right) enQueue(q, node->right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = level;
}
}
return maxLevel;
}using System;
using System.Collections.Generic;
// Definition for a binary tree node.
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MaxLevelSum(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int maxSum = int.MinValue;
int level = 0;
int maxLevel = 0;
while (queue.Count > 0) {
int levelSize = queue.Count;
int levelSum = 0;
level++;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.Dequeue();
levelSum += node.val;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = level;
}
}
return maxLevel;
}
public static void Main(string[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(7);
root.right = new TreeNode(0);
root.left.left = new TreeNode(7);
root.left.right = new TreeNode(-8);
Solution solution = new Solution();
Console.WriteLine("Max Level Sum: " + solution.MaxLevelSum(root));
}
}The Python solution makes use of collections.deque as the queue to perform BFS traversal. The code tracks the sum at each level and determines the maximum sum, updating the level variable whenever a new maximum is found.
Time Complexity: O(n)
Space Complexity: O(m)
Approach 2: Depth-First Search (DFS) with Level Tracking
This approach involves using a DFS traversal to explore the tree. We pass the current depth as a parameter to each recursive call and maintain an array or dictionary to track the sum of values at each level. After the traversal, we determine which level has the highest sum. DFS allows us to explore the tree deeply, and since each call carries a depth count, we can easily track levels.
from collections import defaultdict
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxLevelSum(self, root: TreeNode) -> int:
level_sums = defaultdict(int)
def dfs(node, depth):
if not node:
return
level_sums[depth] += node.val
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 1)
max_level = max(level_sums, key=lambda x: level_sums[x])
return max_level
# Example Usage
root = TreeNode(1)
root.left = TreeNode(7)
root.right = TreeNode(0)
root.left.left = TreeNode(7)
root.left.right = TreeNode(-8)
sol = Solution()
print(sol.maxLevelSum(root))The Python solution uses DFS by recursively traversing the tree and tracking the sum of node values at each level using a dictionary. After completing the traversal, it identifies the level with the maximum sum.
Time Complexity: O(n)
Space Complexity: O(d), where d is the maximum depth of the tree (related to recursion stack depth and level count in the dictionary).
Approach 3: BFS
We use BFS to traverse level by level, calculating the sum of nodes at each level, and find the level with the maximum sum. If there are multiple levels with the maximum sum, return the smallest level number.
Specifically, we use a queue q to store the nodes of the current level. During each traversal, we record the sum of nodes at the current level as s, then add all child nodes of the current level to the queue to prepare for the next level. We use variable mx to record the current maximum sum, and variable ans to record the corresponding level number. After calculating the sum of each level, if s is greater than mx, we update mx and ans. Finally, we return ans.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxLevelSum(root: TreeNode | null): number {
let q = [root];
let i = 0;
let mx = -Infinity;
let ans = 0;
while (q.length) {
++i;
const nq = [];
let s = 0;
for (const { val, left, right } of q) {
s += val;
left && nq.push(left);
right && nq.push(right);
}
if (mx < s) {
mx = s;
ans = i;
}
q = nq;
}
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxLevelSum(root *TreeNode) int {
q := []*TreeNode{root}
mx := -0x3f3f3f3f
i := 0
ans := 0
for len(q) > 0 {
i++
s := 0
for n := len(q); n > 0; n-- {
root = q[0]
q = q[1:]
s += root.Val
if root.Left != nil {
q = append(q, root.Left)
}
if root.Right != nil {
q = append(q, root.Right)
}
}
if mx < s {
mx = s
ans = i
}
}
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;
impl Solution {
pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut q = VecDeque::new();
if let Some(r) = root {
q.push_back(r);
}
let mut i = 0;
let mut mx = i32::MIN;
let mut ans = 0;
while !q.is_empty() {
i += 1;
let mut s = 0;
let sz = q.len();
for _ in 0..sz {
let node = q.pop_front().unwrap();
let node = node.borrow();
s += node.val;
if let Some(left) = node.left.clone() {
q.push_back(left);
}
if let Some(right) = node.right.clone() {
q.push_back(right);
}
}
if s > mx {
mx = s;
ans = i;
}
}
ans
}
}Approach 4: DFS
We can also use DFS to solve this problem. We use an array s to store the sum of nodes at each level. The index of the array represents the level, and the value of the array represents the sum of nodes. We use DFS to traverse the binary tree, adding the value of each node to the sum of nodes at the corresponding level. Finally, we return the index corresponding to the maximum value in s.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxLevelSum(root *TreeNode) int {
s := []int{}
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, i int) {
if root == nil {
return
}
if len(s) == i {
s = append(s, root.Val)
} else {
s[i] += root.Val
}
dfs(root.Left, i+1)
dfs(root.Right, i+1)
}
dfs(root, 0)
ans, mx := 0, -0x3f3f3f3f
for i, v := range s {
if mx < v {
mx = v
ans = i + 1
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) |
| Depth-First Search (DFS) with Level Tracking | Time Complexity: O(n) |
| BFS | – |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(w) | Best for problems involving level-by-level processing of a binary tree |
| Depth-First Search with Level Tracking | O(n) | O(h) + O(L) | Useful when implementing recursive traversal or when tracking level data during DFS |
Frequently asked questions
Is Maximum Level Sum of a Binary Tree easy or hard?
Maximum Level Sum of a Binary Tree is considered a Medium difficulty problem on LeetCode. The logic is straightforward if you understand BFS level-order traversal, but recognizing the level-based processing pattern is the key challenge.
Maximum Level Sum of a Binary Tree Python/Java solution
Python and Java implementations typically use BFS with a queue. Each iteration processes all nodes at the current level, calculates the sum, and enqueues child nodes. The same logic can be implemented in C++, C#, and JavaScript with similar queue-based structures.
How to solve Maximum Level Sum of a Binary Tree in O(n)?
Traverse the tree once and accumulate the sum of node values for each level. Using BFS, process nodes in a queue level by level and track the maximum sum encountered. Using DFS, store cumulative sums in an array indexed by depth and compute the maximum after traversal.
What is the best approach for Maximum Level Sum of a Binary Tree?
Breadth-First Search (BFS) using level-order traversal is the most common solution. A queue processes nodes level by level, allowing you to compute the sum of each level in one pass. This approach runs in O(n) time and uses O(w) space where w is the maximum width of the tree.
Is Maximum Level Sum of a Binary Tree asked at Google/Amazon/Meta?
Tree traversal problems that involve level processing frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of level-order traversal and BFS-based tree aggregation are common interview patterns.
What data structure is used in Maximum Level Sum of a Binary Tree?
The BFS approach relies on a queue to perform level-order traversal. The DFS approach uses recursion and an array or list to store sums for each level while traversing the tree.
What is the time complexity of Maximum Level Sum of a Binary Tree?
The optimal solutions run in O(n) time because every node in the binary tree is visited exactly once. BFS processes nodes level by level, while DFS processes nodes through recursion but still touches each node once.