1161. Maximum Level Sum of a Binary Tree

Problem Description

Given the root of a binary tree, find the smallest level x where the sum of node values at that level is maximal. The root is at level 1, its children at level 2, and so on.

Solution Approaches

This problem can be solved using either Breadth-First Search (BFS) or Depth-First Search (DFS). Both approaches have a time complexity of O(N), where N is the number of nodes in the tree. The space complexity also depends on the tree's structure; in the worst case (a complete binary tree), it's O(N) for BFS due to the queue and O(H) for DFS due to the recursion stack, where H is the height of the tree (log N for a balanced tree, N for a skewed tree).

Approach 1: Breadth-First Search (BFS)

BFS is generally preferred for level-order traversal because it directly processes nodes level by level.

1. Initialization: Create a queue q to store nodes, initialize max_sum to negative infinity, level to 0, and result_level to 0.
2. Iteration: While the queue is not empty:
   • Increment level.
   • Create a variable current_sum to store the sum of nodes at the current level.
   • Process all nodes at the current level:
     • Dequeue a node from q.
     • Add its value to current_sum.
     • Enqueue its left and right children (if not null).
   • If current_sum is greater than max_sum:
     • Update max_sum to current_sum.
     • Update result_level to level.
3. Return: Return result_level.

Approach 2: Depth-First Search (DFS)

DFS can also be adapted to solve this problem, although it's less intuitive for level-order processing.

1. Initialization: Create an array level_sums to store the sum of nodes at each level. Initialize it as an empty list or array.
2. Recursive Function: Define a recursive function dfs(node, level):
   • Base Case: If node is null, return.
   • Update level_sums: If level is less than the size of level_sums, add the node's value to the existing sum at level; otherwise, append the node's value as a new sum at level.
   • Recursively call dfs for the left and right children, incrementing level.
3. Post-processing: After the recursive calls complete, find the maximum sum in level_sums and return its index + 1 (to account for 1-based indexing of levels).

Code Implementations

Python3 (BFS)

from collections import deque
 
def maxLevelSum(root):
    q = deque([root])
    max_sum = float('-inf')
    level = 0
    result_level = 0
    while q:
        level += 1
        current_sum = 0
        for _ in range(len(q)):
            node = q.popleft()
            current_sum += node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        if current_sum > max_sum:
            max_sum = current_sum
            result_level = level
    return result_level
 

Java (DFS)

import java.util.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    List<Integer> levelSums = new ArrayList<>();
 
    public int maxLevelSum(TreeNode root) {
        dfs(root, 0);
        int maxSum = Integer.MIN_VALUE;
        int maxLevel = 0;
        for (int i = 0; i < levelSums.size(); i++) {
            if (levelSums.get(i) > maxSum) {
                maxSum = levelSums.get(i);
                maxLevel = i + 1;
            }
        }
        return maxLevel;
    }
 
    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (level >= levelSums.size()) {
            levelSums.add(node.val);
        } else {
            levelSums.set(level, levelSums.get(level) + node.val);
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

Other languages (C++, Go, TypeScript) would follow similar structures for both BFS and DFS approaches. The core logic remains the same; only the syntax and data structures vary.