Maximum Level Sum of a Binary Tree - Practice Coding Problems

Maximum Level Sum of a Binary Tree - 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.

Input & Output

Example 1 — Basic Case

$ Input: root = [1,7,0,7,-8,null,null]

› Output: 2

💡 Note: Level 1: sum = 1. Level 2: sum = 7 + 0 = 7. Level 3: sum = 7 + (-8) = -1. Maximum sum is 7 at level 2.

Example 2 — Single Node

$ Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]

› Output: 2

💡 Note: Level 1: sum = 989. Level 2: sum = 10250. Level 3: sum = 98693 + (-89388) = 9305. Level 4: sum = -32127. Maximum sum is 10250 at level 2.

Example 3 — Negative Values

$ Input: root = [-100,-200,-300,-20,-5,-10,null]

› Output: 3

💡 Note: Level 1: sum = -100. Level 2: sum = -200 + (-300) = -500. Level 3: sum = -20 + (-5) + (-10) = -35. Maximum sum is -35 at level 3.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes containing integer values

Level Sums

Calculate sum for each level of the tree

Maximum Level

Return the smallest level number with maximum sum

Key Takeaway

🎯 Key Insight: BFS naturally processes nodes level by level, making it perfect for calculating level sums efficiently

Asked in

f Facebook 25 a Amazon 20 M Microsoft 15 G Google 12

The key insight is to use BFS (breadth-first search) to naturally process nodes level by level, calculating the sum for each complete level and tracking which level has the maximum sum. The optimal approach uses a queue to implement BFS traversal. Time: O(n), Space: O(w) where w is the maximum width of the tree.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Level Tracking	O(n)	O(h + l)	Use DFS to traverse and track sum at each level with a map
BFS Level Order Traversal	O(n)	O(w)	Use BFS to process nodes level by level and track maximum sum

DFS with Level Tracking — Algorithm Steps

Step 1: Use DFS to visit each node with its level
Step 2: Store level sums in hash map
Step 3: Find level with maximum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit each node and track its level

Sum Accumulation

Add node values to their respective level sums

Find Maximum

Return the level with maximum sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct LevelSum {
    int level;
    int sum;
};

struct LevelSum levelSums[1000];
int levelCount = 0;

void dfs(struct TreeNode* node, int level) {
    if (!node) return;
    
    int found = 0;
    for (int i = 0; i < levelCount; i++) {
        if (levelSums[i].level == level) {
            levelSums[i].sum += node->val;
            found = 1;
            break;
        }
    }
    
    if (!found) {
        levelSums[levelCount].level = level;
        levelSums[levelCount].sum = node->val;
        levelCount++;
    }
    
    dfs(node->left, level + 1);
    dfs(node->right, level + 1);
}

int solution(struct TreeNode* root) {
    if (!root) return 1;
    
    levelCount = 0;
    dfs(root, 1);
    
    int maxSum = INT_MIN;
    int resultLevel = 1;
    
    for (int i = 0; i < levelCount; i++) {
        if (levelSums[i].sum > maxSum) {
            maxSum = levelSums[i].sum;
            resultLevel = levelSums[i].level;
        }
    }
    
    return resultLevel;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // For simplicity, create a sample tree [1,7,0,7,-8,null,null]
    struct TreeNode* root = createNode(1);
    root->left = createNode(7);
    root->right = createNode(0);
    root->left->left = createNode(7);
    root->left->right = createNode(-8);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once during DFS traversal

✓ Linear Growth

Space Complexity

O(h + l)

Recursion stack depth h plus hash map for l levels

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

945 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Level Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler