Easy O(n) Python DFS/BFS Solution 
IntuitionThe problem asks us to find the level in a binary tree with the maximum sum of node values. Each level is like a row in the tree, and we need to calcul
# Intuition
The problem asks us to find the level in a binary tree with the maximum sum of node values. Each level is like a row in the tree, and we need to calculate the sum of values for each row and determine which row (level) has the highest sum.

---

# Approaches

## 1. DFS (Depth-First Search):
1. Use a `defaultdict` to store the sum of node values at each depth (level).
2. Traverse the tree using DFS, adding the value of each node to the corresponding level in the dictionary.
3. After the traversal, find the level with the maximum sum using `max()` on the dictionary.

## 2. BFS (Breadth-First Search):
1. Use a queue to traverse the tree level by level.
2. At each level, calculate the sum of node values.
3. Track the maximum sum and its corresponding level.
4. Continue until all levels are processed.

---

# Complexity
- **Time Complexity**:  
  $$O(n)$$ for both DFS and BFS, where $$n$$ is the number of nodes in the tree. Each node is visited exactly once.

- **Space Complexity**:  
  - DFS: $$O(n)$$ (or $$O(h)$$, where $$h$$ is the height of the tree (recursion stack))
  - BFS: $$O(n)$$ (or $$O(w)$$, where $$w$$ is the maximum width of the tree (queue size))

---

# Code

## DFS Solution
```python3
# 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

from collections import defaultdict

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        sumAtDepth = defaultdict(int)

        # DFS function to calculate sum at each depth
        def dfs(node, depth):
            if not node:
                return
            
            # Add current node's value to its depth's sum
            sumAtDepth[depth] += node.val

            # Recur for left and right children
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        # Start DFS from root at depth 1
        dfs(root, 1)

        # Return the level with the maximum sum
        return max(sumAtDepth, key=sumAtDepth.get)
```

## BFS Solution

```python3
# 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

from collections import defaultdict

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        maxSum = root.val
        resDepth = 1

        queue = deque([root])
        depth = 1

        # Perform BFS
        while queue:
            currSum = 0
            for _ in range(len(queue)):  # Iterate through nodes in the current level
                node = queue.popleft()
                currSum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Update maximum sum and result level
            if currSum > maxSum:
                maxSum = currSum
                resDepth = depth
            
            # Move to the next level
            depth += 1

        return resDepth
```
['Python3']