Find the Level of Tree with Minimum Sum - Practice Coding Problems

Find the Level of Tree with Minimum Sum - Problem

Given the root of a binary tree where each node has a value, return the level of the tree that has the minimum sum of values among all the levels.

In case of a tie, return the lowest level. Note that the root of the tree is at level 1 and the level of any other node is its distance from the root + 1.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Level 1: sum = 1, Level 2: sum = 7+0 = 7, Level 3: sum = 7+(-8) = -1. Level 3 has the minimum sum of -1.

Example 2 — Single Node

$ Input: root = [5]

› Output: 1

💡 Note: Only one level with sum = 5, so return level 1.

Example 3 — Tie Case

$ Input: root = [1,2,3,4,5,6,7]

› Output: 1

💡 Note: Level 1: sum = 1, Level 2: sum = 2+3 = 5, Level 3: sum = 4+5+6+7 = 22. Level 1 has minimum sum.

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 node values [1,7,0,7,-8,null,null]

Level Sums

Calculate sum for each level: L1=1, L2=7, L3=-1

Find Minimum

Level 3 has minimum sum of -1

Key Takeaway

🎯 Key Insight: Use level-order traversal to process complete levels and track minimum sum

Asked in

a Amazon 25 M Microsoft 18

The key insight is to process the binary tree level by level to calculate the sum at each level, then find the level with minimum sum. Best approach is BFS level-order traversal which naturally processes complete levels. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Level Tracking	O(n)	O(h + d)	Use DFS to traverse all nodes and track sum at each level
Level-Order BFS	O(n)	O(w)	Use BFS to process nodes level by level and calculate sums

DFS with Level Tracking — Algorithm Steps

Step 1: DFS traverse the tree with level parameter
Step 2: Accumulate sums for each level in a map
Step 3: Find level with minimum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit each node with its level

Sum Calculation

Accumulate values at each level

Find Minimum

Return level with minimum 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;
};

typedef struct {
    int level;
    long long sum;
} LevelSum;

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);
    
    long long minSum = LLONG_MAX;
    int minLevel = 1;
    
    for (int i = 0; i < levelCount; i++) {
        if (levelSums[i].sum < minSum || 
           (levelSums[i].sum == minSum && levelSums[i].level < minLevel)) {
            minSum = levelSums[i].sum;
            minLevel = levelSums[i].level;
        }
    }
    
    return minLevel;
}

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

int main() {
    printf("1\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during DFS traversal

✓ Linear Growth

Space Complexity

O(h + d)

O(h) for recursion stack depth, O(d) for storing sums of d levels

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 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