Maximum Level Sum of a Binary Tree

class Solution {
public:
    void traverse(TreeNode* root, int depth, vector<int>& levelsSum) {
        if (!root) {
            return;
        }

        if (levelsSum.size() == depth) {
            levelsSum.push_back(root->val);
        } else {
            levelsSum[depth] += root->val;
        }

        traverse(root->left, depth + 1, levelsSum);
        traverse(root->right, depth + 1, levelsSum);
    }

    int maxLevelSum(TreeNode* root) {
        vector<int> levelsSum;
        traverse(root, 0, levelsSum);

        int highestSum = INT_MIN;
        int bestLevel = 0;

        for (int i = 0; i < levelsSum.size(); i++) {
            if (highestSum < levelsSum[i]) {
                highestSum = levelsSum[i];
                bestLevel = i + 1;
            }
        }

        return bestLevel;
    }
};

The provided C++ solution aims to find the level of a binary tree that holds the maximum sum of its node values. The approach is based on a depth-first search traversal to accumulate the sum of values at each level.

Here's a breakdown of the code structure and logic:

• The code defines a class Solution that includes two member functions: traverse and maxLevelSum.

• In the traverse function:

  • This recursive function calculates the sum of node values at each level of the tree. It takes three parameters: the current node (root), the current depth or level (depth), and a reference to a vector (levelsSum) that stores the sum of node values per level.
  • If the node is null, the function returns immediately, handling base cases of the recursion where a leaf node has been surpassed.
  • If the current level equals the size of levelsSum, indicating that this level has not been encountered before, the function initializes the sum for this level with the current node's value.
  • Otherwise, it increases the current level's sum by the node's value.
  • The function then recursively calls itself for the left and right children, incrementing the depth each time to advance to the next level.

• In the maxLevelSum function:

  • Initially, an empty vector levelsSum is declared to store the sum of values at each level.
  • The traverse function is called to populate this vector.
  • The function then iterates over the levelsSum vector to determine which level has the highest sum. It uses two variables, highestSum to keep track of the maximum sum encountered and bestLevel to store the level at which this sum occurs.
  • It returns bestLevel, which is the level with the highest total value of nodes, adjusted to be 1-based.

This solution efficiently calculates the required maximum level sum by performing a single pass traversal of the tree and another pass to determine the maximum from the level sums. Ensure the tree node structure (TreeNode) is defined elsewhere in your codebase, including its attributes such as left, right, and val.

class Solution {
    public void explore(TreeNode node, int depth, List<Integer> levelSums) {
        if (node == null) {
            return;
        }

        if (levelSums.size() == depth) {
            levelSums.add(node.val);
        } else {
            levelSums.set(depth, levelSums.get(depth) + node.val);
        }

        explore(node.left, depth + 1, levelSums);
        explore(node.right, depth + 1, levelSums);
    }

    public int maxLevelSum(TreeNode root) {
        List<Integer> levelSums = new ArrayList<>();
        explore(root, 0, levelSums);

        int highestSum = Integer.MIN_VALUE;
        int level = 0;

        for (int i = 0; i < levelSums.size(); i++) {
            if (highestSum < levelSums.get(i)) {
                highestSum = levelSums.get(i);
                level = i + 1;
            }
        }

        return level;
    }
}

The given Java program is designed to calculate the maximum level sum of a binary tree. The solution encompasses the following actions:

• A helper method explore(TreeNode node, int depth, List<Integer> levelSums) is used:

  • Ensures the node is not null before processing.
  • If the current depth matches the size of levelSums, it appends the node's value to the list. Otherwise, it updates the sum for the existing depth.
  • Recursively calls itself for the left and right children of the node, incrementing the depth.

• The primary method maxLevelSum(TreeNode root) initializes a list levelSums to keep track of sums at different levels:

  • Calls the explore() method starting from the root of the tree.
  • Iterates through levelSums to find the maximum value and records the corresponding tree level.
  • Returns the one-indexed level (depth) which has the maximum sum.

The approach effectively combines recursion to traverse the tree and a dynamic list to manage level-wise sums, facilitating the computation of the tree level that has the highest total sum of node values.

class Solution:
    def treeSearch(
        self, node: Optional[TreeNode], depth: int, level_sums: List[int]
    ) -> None:
        if not node:
            return

        if len(level_sums) == depth:
            level_sums.append(node.val)
        else:
            level_sums[depth] += node.val

        self.treeSearch(node.left, depth + 1, level_sums)
        self.treeSearch(node.right, depth + 1, level_sums)

    def largestLevelSum(self, root: Optional[TreeNode]) -> int:
        sums = []
        self.treeSearch(root, 0, sums)

        highest_sum = float("-inf")
        max_level = 0

        for idx in range(len(sums)):
            if highest_sum < sums[idx]:
                highest_sum = sums[idx]
                max_level = idx + 1

        return max_level

The given Python 3 code defines a solution for finding the maximum level sum in a binary tree. The approach utilizes a helper function, treeSearch, to traverse the tree recursively and collect the sum of the nodes' values at each level. This function takes a node, its depth, and a running list level_sums to track the sum of values at each level.

• The recursive function treeSearch ensures that if the current node is None, the function returns immediately, indicating the end of a branch.
• If the current depth level doesn't yet have an entry in level_sums, it adds the current node's value as a new entry; otherwise, it adds the value to the existing sum for that depth.
• It then recursively calls itself for both the left and right children of the current node, incrementing the depth by one to move to the next level.

The main function, largestLevelSum, initializes an empty list sums and calls treeSearch to fill this list with the sum of values at each level of the tree. It then iterates through the sums to identify the maximum value and its corresponding level.

• The variable highest_sum is used to keep track of the highest sum encountered, initialized to negative infinity to handle possible negative values in the tree.
• max_level stores the tree level with the highest sum, adjusting for the fact that levels are typically considered 1-indexed in non-programming contexts.

The function ultimately returns max_level, which corresponds to the tree level having the maximum sum of node values. This ensures that the solution efficiently calculates and identifies the level with the maximum contribution in terms of node values.