BEATS 97% | EASY AND DETAILED EXPLANATION
Intuition:\nThe problem is asking for the level in a binary tree that has the maximum sum of node values. To solve this, we need to explore the tree level by le
### Intuition:\nThe problem is asking for the level in a binary tree that has the maximum sum of node values. To solve this, we need to explore the tree level by level and keep track of the sum of the nodes at each level. Once we have the sums for all levels, we can compare them and return the level that has the highest sum.\n\nThis problem can be efficiently tackled using **Breadth-First Search (BFS)**. BFS is ideal for level-order traversal in a tree. Using a queue, we can process nodes level by level, calculate the sum of the node values at each level, and compare that sum to find the maximum sum across all levels.\n\n### Approach:\n1. **Breadth-First Search (BFS) for Level Order Traversal**:\n   We traverse the tree level by level using a queue. Nodes at each level are processed together before moving to the next level.\n   \n2. **Sum Calculation for Each Level**:\n   While processing each level, we sum up the values of the nodes at that level. After processing each level, we compare the current sum with the maximum sum seen so far.\n\n3. **Tracking the Maximum Level**:\n   We keep track of which level has the highest sum. The first level is level 1. Each time we process a level, we update the `maxLevel` if the sum of that level is higher than any previous level.\n\n4. **Queue for BFS**:\n   We use a queue (implemented as an array in this case) to store nodes of the current level, process them, and add their children (the next level) to the queue.\n\n### Dry Run:\n\nLet\'s walk through an example step by step.\n\n#### Test Case:\n```\nroot = [1, 7, 0, 7, -8, null, null]\n```\n\nThis tree looks like:\n```\n        1\n       / \\\n      7   0\n     / \\\n    7  -8\n```\n\n- **Initial State**:\n  - Queue: [1] (contains the root node)\n  - `head = 0`, `tail = 1`, `maxSum = -\u221E`, `maxLevel = 0`\n  - Current level: 1\n\n### Step 1: Process Level 1\n- Nodes at level 1: [1]\n- Sum for level 1: 1\n- Max sum becomes 1, max level is updated to 1.\n  \n  Queue after processing level 1:\n  - Queue: [7, 0] (left and right children of 1)\n  - `head = 1`, `tail = 3`\n  - `maxSum = 1`, `maxLevel = 1`\n  - Move to next level: level 2\n\n### Step 2: Process Level 2\n- Nodes at level 2: [7, 0]\n- Sum for level 2: 7 + 0 = 7\n- Max sum becomes 7, max level is updated to 2.\n\n  Queue after processing level 2:\n  - Queue: [7, -8] (children of nodes at level 2)\n  - `head = 3`, `tail = 5`\n  - `maxSum = 7`, `maxLevel = 2`\n  - Move to next level: level 3\n\n### Step 3: Process Level 3\n- Nodes at level 3: [7, -8]\n- Sum for level 3: 7 + (-8) = -1\n- Max sum remains 7 (level 2 had the higher sum).\n\n  Queue after processing level 3:\n  - Queue: [] (no more nodes to process)\n  - `head = 5`, `tail = 5`\n  - End of traversal since the queue is empty.\n\n### Conclusion:\nThe level with the maximum sum is **level 2**.\n\n### Complexity:\n\n1. **Time Complexity**:\n   - We are traversing all nodes of the tree exactly once.\n   - If the tree has `n` nodes, the time complexity is **O(n)** because each node is visited once during the BFS traversal.\n  \n2. **Space Complexity**:\n   - We are using a queue to store the nodes of the tree level by level. In the worst case, the queue could store all nodes at the bottom-most level, which can be up to `n/2` nodes in a complete binary tree.\n   - Therefore, the space complexity is **O(n)**.\n\n### Code:\n\n```java\nclass Solution {\n    public int maxLevelSum(TreeNode root) {\n        TreeNode[] queue = new TreeNode[100001];  // Queue for BFS\n        int head = 0;  // Points to the node we are currently processing\n        int tail = 0;  // Points to the next free space in the queue\n\n        int maxSum = Integer.MIN_VALUE;  // To store the maximum sum encountered\n        int maxLevel = 0;  // To store the level with the maximum sum\n\n        queue[tail++] = root;  // Start BFS by adding the root node to the queue\n        int level = 1;  // Start at level 1\n\n        // BFS loop\n        while (head < tail) {\n            int count = tail - head;  // Number of nodes at the current level\n            int tempSum = 0;  // Sum of nodes at the current level\n\n            // Process all nodes at the current level\n            for (int i = 0; i < count; i++) {\n                TreeNode currentNode = queue[head++];  // Get the next node\n                tempSum += currentNode.val;  // Add its value to the sum\n\n                // Add its children (next level) to the queue\n                if (currentNode.left != null) {\n                    queue[tail++] = currentNode.left;\n                }\n\n                if (currentNode.right != null) {\n                    queue[tail++] = currentNode.right;\n                }\n            }\n\n            // Update maxSum and maxLevel if this level\'s sum is greater\n            if (tempSum > maxSum) {\n                maxSum = tempSum;\n                maxLevel = level;\n            }\n\n            level++;  // Move to the next level\n        }\n\n        return maxLevel;  // Return the level with the maximum sum\n    }\n}\n```\n\n### Visualization of the Dry Run:\n\n1. **Before Level 1**:\n   - Queue: [1]\n   - Level sum: 1\n   - Max sum: -\u221E \u2192 1, Max level: 1\n\n2. **Before Level 2**:\n   - Queue: [7, 0]\n   - Level sum: 7\n   - Max sum: 1 \u2192 7, Max level: 2\n\n3. **Before Level 3**:\n   - Queue: [7, -8]\n   - Level sum: -1\n   - Max sum remains 7\n\nIn the end, level 2 has the maximum sum.
['Java']