# Maximum Level Sum of a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-level-sum-of-a-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, 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**.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-level-sum-of-a-binary-tree/image0.JPG) 

**Input:** root = [1,7,0,7,-8,null,null]
**Output:** 2
**Explanation:** 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

**Example 2:**

**Input:** root = [989,null,10250,98693,-89388,null,null,null,-32127]
**Output:** 2

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `-105 <= Node.val <= 105`

# Approaches
## Depth-First Search (DFS)
This approach uses a recursive Depth-First Search traversal to visit every node. We pass the current level as an argument in the recursive calls. A list is used to store the sum of node values for each level. After the traversal is complete, we iterate through this list to find the level with the maximum sum.
**Time:** O(N), where N is the number of nodes in the tree. The DFS traversal takes O(N) time as it visits each node once. The subsequent loop to find the maximum sum takes O(H) time, where H is the height of the tree. Thus, the total time is O(N + H), which simplifies to O(N). · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack and the `levelSums` list, both of which can grow up to the height of the tree. In the worst case of a skewed tree, H can be N, making the space complexity O(N).
**Pros:** Conceptually simple if you are very familiar with DFS and recursion.
**Cons:** Requires two passes over the data: one to traverse the tree and populate the sums, and a second to iterate through the sums to find the maximum.; Less intuitive for a level-by-level problem compared to BFS.; Space complexity can be O(N) for skewed trees, which is worse than BFS for that specific case.
### Explanation
This approach utilizes a Depth-First Search (DFS) traversal to compute the sum of nodes at each level. We use a recursive helper function that takes the current node and its level as arguments. An external data structure, like an `ArrayList`, is used to store the sum for each level. The index of the list corresponds to the level number (minus one). As the DFS traversal explores the tree, it populates this list with the sums. Once the traversal is complete, we perform a second pass over the list of sums to identify the maximum sum and the smallest level at which it occurs.

Here is the Java implementation:
```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 Solution {
    private List<Integer> levelSums = new ArrayList<>();

    public int maxLevelSum(TreeNode root) {
        dfs(root, 1);

        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 - 1, levelSums.get(level - 1) + node.val);
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}
```
### Algorithm
- Initialize an empty list, `levelSums`, to store the sum of nodes for each level.
- Define a recursive helper function `dfs(node, level)`.
- In `dfs(node, level)`:
    - Base case: If `node` is null, return.
    - If `level` is greater than the current size of `levelSums`, add `node.val` as a new entry.
    - Otherwise, update the sum at index `level - 1` by adding `node.val`.
    - Recursively call `dfs` for the left child with `level + 1`.
    - Recursively call `dfs` for the right child with `level + 1`.
- Start the traversal by calling `dfs(root, 1)`.
- After the traversal, iterate through `levelSums` to find the maximum sum.
- Keep track of the index `i` where the maximum sum is found. The first such index will correspond to the smallest level.
- Return `i + 1` as the result.

## Breadth-First Search (BFS)
This approach uses Breadth-First Search (BFS), which is the natural way to traverse a tree level by level. We use a queue to process nodes. In each iteration of the main loop, we process all nodes of a single level, calculate their sum, and compare it with the maximum sum found so far.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the binary tree. The space is dominated by the queue, which holds at most all nodes of the widest level. In the worst case (a complete binary tree), W can be up to N/2, making the space complexity O(N).
**Pros:** Very intuitive for a level-order problem.; Calculates the sum and finds the maximum in a single pass.; Naturally finds the smallest level in case of ties because levels are processed in order.; More space-efficient than DFS for tall, skinny trees.
**Cons:** Can be less space-efficient than DFS for short, wide trees (e.g., complete binary trees where space is O(N) vs DFS's O(log N)).
### Explanation
This approach uses Breadth-First Search (BFS), which is a natural fit for problems involving tree levels. By using a queue, we can process the tree one level at a time. We iterate through the levels, and for each level, we calculate the sum of its node values. We maintain a variable to track the maximum sum seen so far and the level at which it occurred. Since we process levels in increasing order (1, 2, 3, ...), the first time we find a maximum sum, we record its level. Any subsequent levels with the same maximum sum will be ignored, automatically satisfying the condition to return the smallest level. This method efficiently finds the result in a single pass over the tree.

Here is the Java implementation:
```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 Solution {
    public int maxLevelSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int maxSum = Integer.MIN_VALUE;
        int resultLevel = 0;
        int currentLevel = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int currentLevelSum = 0;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevelSum += node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (currentLevelSum > maxSum) {
                maxSum = currentLevelSum;
                resultLevel = currentLevel;
            }
            currentLevel++;
        }
        return resultLevel;
    }
}
```
### Algorithm
- Handle the edge case where the `root` is null.
- Initialize a `Queue` and add the `root` node.
- Initialize variables: `maxSum` to a very small number, `resultLevel = 1`, and `currentLevel = 1`.
- Begin a loop that continues as long as the queue is not empty.
- Inside the loop, first determine the number of nodes at the current level by getting the queue's size (`levelSize`).
- Initialize `currentLevelSum = 0`.
- Start an inner loop that runs `levelSize` times to process all nodes of the current level:
    - Dequeue a node from the queue.
    - Add the node's value to `currentLevelSum`.
    - Enqueue the node's non-null left and right children.
- After the inner loop, compare `currentLevelSum` with `maxSum`. If it's greater, update `maxSum` and set `resultLevel` to `currentLevel`.
- Increment `currentLevel` for the next iteration.
- After the main loop finishes, return `resultLevel`.

# Solutions
### Java

```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 Solution { public int maxLevelSum ( TreeNode root ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int mx = Integer . MIN_VALUE ; int i = 0 ; int ans = 0 ; while (! q . isEmpty ()) { ++ i ; int s = 0 ; for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . pollFirst (); s += node . val ; if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } if ( mx < s ) { mx = s ; ans = i ; } } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxLevelSum ( TreeNode * root ) { queue < TreeNode *> q { { root } }; int mx = INT_MIN ; int ans = 0 ; int i = 0 ; while ( ! q . empty ()) { ++ i ; int s = 0 ; for ( int n = q . size (); n ; -- n ) { root = q . front (); q . pop (); s += root -> val ; if ( root -> left ) q . push ( root -> left ); if ( root -> right ) q . push ( root -> right ); } if ( mx < s ) mx = s , ans = i ; } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxLevelSum ( self , root : Optional [ TreeNode ]) -> int : q = deque ([ root ]) mx = - inf i = 0 while q : i += 1 s = 0 for _ in range ( len ( q )): node = q . popleft () s += node . val if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) if mx < s : mx = s ans = i return ans
```