BETTER THAN EDITORIAL Two Solutions Beats 100%
1161. Maximum Level Sum of a Binary Tree🔹 Solution 1: BFS with Two Lists (Optimized & 100% Faster)✅ Why This Works (and is 100% Faster)
Uses two lists (current_
# 1161. Maximum Level Sum of a Binary Tree

---

# 🔹 Solution 1: BFS with Two Lists (Optimized & 100% Faster)

---

## ✅ Why This Works (and is 100% Faster)
- Uses two lists (current_level_nodes and next_level_nodes) instead of a queue.
- Efficiently tracks level-wise nodes without extra dictionary lookups.
- Uses sum(node.val for node in current_level_nodes) to compute level sum directly.
- Time Complexity: O(N), visiting each node once.
- Space Complexity: O(W), where W is the maximum width of the tree.

---


```python
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        assert root is not None  # Ensure input is valid
        
        current_level_nodes = [root]  # Track nodes at the current level
        next_level_nodes = []  # Prepare for the next level
        level = 0  # Track the current level (0-based index)
        max_level = 0  # Store the level with the max sum
        max_sum = root.val  # Initialize max sum with root's value

        while current_level_nodes:
            level_sum = sum(node.val for node in current_level_nodes)  # Sum of current level
            
            # Check if the new level has a higher sum
            if level_sum > max_sum:
                max_sum = level_sum
                max_level = level  # Update max level

            # Prepare the next level nodes
            for node in current_level_nodes:
                if node.left:
                    next_level_nodes.append(node.left)
                if node.right:
                    next_level_nodes.append(node.right)

            # Move to the next level
            current_level_nodes, next_level_nodes = next_level_nodes, []
            level += 1
        
        return max_level + 1  # Convert 0-based index to 1-based level
```

---

## 🔹 Solution 2: BFS with `deque` and `defaultdict` (Simple & Efficient)

---

### ✅ Why This Works
- BFS traversal ensures level-wise processing.
- defaultdict(int) keeps track of sum per level.
- Uses max(level_sums, key=level_sums.get) to find the level with the highest sum.
- Time Complexity: O(N), since we visit each node once.
- Space Complexity: O(N), for storing level sums.


---


```python
from collections import deque, defaultdict

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        level_sums = defaultdict(int)  # Dictionary to store sum per level
        q = deque([(root, 1)])  # Queue to track (node, level)

        while q:
            node, level = q.popleft()
            level_sums[level] += node.val

            if node.left:
                q.append((node.left, level + 1))
            if node.right:
                q.append((node.right, level + 1))

        # Find the level with the maximum sum
        return max(level_sums, key=level_sums.get)

['Python3']