1161. Maximum Level Sum of a Binary Tree

Description

The problem requires finding the level in a binary tree that has the maximum sum of node values. The binary tree is traversed level by level, and the sum of node values for each level is calculated. The level with the highest sum is returned as the result.

Intuition

To solve this problem, the key idea is to leverage the level order traversal (breadth-first traversal) of the binary tree. As we traverse each level, we calculate the sum of node values and keep track of the maximum sum encountered. The level corresponding to this maximum sum is the desired output.

Approach

1. Initialization: - Start by initializing an empty list or array sums to store the sum of node values for each level. - Perform a level order traversal of the binary tree.
2. Traversal: - Use a recursive or iterative method to traverse the binary tree. At each node, calculate the depth (or level) and add the node's value to the corresponding index in the sums list. - If the list does not have an entry for the current level, extend it.
3. Compute Maximum: - Once the entire tree has been traversed, find the maximum value in the sums list. - The index of this maximum value in the list corresponds to the level with the maximum sum.
4. Return the Result: - Since levels are 1-indexed, return the index of the maximum value plus one.

Complexity

Time Complexity:

The algorithm performs a single traversal of the tree, making the time complexity O(N), where N is the number of nodes in the tree.

Space Complexity:

The space complexity is O(H), where H is the height of the tree, due to the recursive stack or the queue used in level order traversal.

Code

C++

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        vector sums;
        traverse(root, 0, sums);
        return max_element(sums.begin(), sums.end()) - sums.begin() + 1;
    }
    
private:
    void traverse(TreeNode* node, int depth, vector& sums) {
        if (!node) return;
        
        if (sums.size() == depth) {
            sums.push_back(0);
        }
        
        sums[depth] += node->val;
        
        traverse(node->left, depth + 1, sums);
        traverse(node->right, depth + 1, sums);
    }
};

Python

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        sums = []
        
        def traverse(node, depth):
            if not node:
                return
            
            if len(sums) == depth:
                sums.append(0)
            
            sums[depth] += node.val
            
            traverse(node.left, depth + 1)
            traverse(node.right, depth + 1)
        
        traverse(root, 0)
        return sums.index(max(sums)) + 1

Java

/**
 * Definition for a binary tree node.
 * public 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 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 {
    public int maxLevelSum(TreeNode root) {
        List sums = new ArrayList<>();
        traverse(root, 0, sums);
        return sums.indexOf(Collections.max(sums)) + 1;
    }

    private void traverse(TreeNode node, int depth, List sums) {
        if (node == null) return;
        
        if (depth >= sums.size()) {
            sums.add(0);
        }
        
        sums.set(depth, sums.get(depth) + node.val);
        
        traverse(node.left, depth + 1, sums);
        traverse(node.right, depth + 1, sums);
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var maxLevelSum = function(root) {
    const sums = [];

    const traverse = (node, depth) => {
        if (!node) {
            return;
        }

        sums[depth] = (sums[depth] ?? 0) + node.val;

        traverse(node.left, depth + 1);
        traverse(node.right, depth + 1);
    }
    traverse(root, 0);
    return sums.findIndex((el) =>  el === Math.max(...sums)) + 1;
};