BFS Solution || Easy to Understand
Approach\n\n\nThe given code is a Java implementation of a solution to find the level with the maximum sum in a binary tree. Here\'s the approach:\n\n1. Initial
# Approach\n\n\nThe given code is a Java implementation of a solution to find the level with the maximum sum in a binary tree. Here\'s the approach:\n\n1. Initialize a queue to hold the nodes of the tree, and add the root node to it.\n2. Initialize a variable `level` to 1, which will keep track of the current level being processed.\n3. Initialize two variables, `max` and `maxlevel`, to `Integer.MIN_VALUE` and 1 respectively. These variables will keep track of the maximum sum seen so far and the level where it was seen.\n4. While the queue is not empty, perform the following steps:\n   a. Get the size of the queue.\n   b. Initialize a variable `sum` to 0, which will keep track of the sum of the nodes at the current level.\n   c. For each node at the current level, remove it from the queue, add its value to `sum`, and add its children (if any) to the queue.\n   d. If `sum` is greater than `max`, update `max` to `sum` and `maxlevel` to `level`.\n   e. Increment `level`.\n5. Return `maxlevel` as the level with the maximum sum.\n\nThe code uses a standard BFS approach to traverse the binary tree and calculate the sum of nodes at each level. The level variable is incremented after processing each level, ensuring that the level with the maximum sum is correctly identified. The final result returned is the level with the maximum sum.\n\n# Complexity\nThe time and space complexities of the provided code are as follows:\n\n1. Time Complexity: O(N)\n   - The code traverses all the nodes of the binary tree using a breadth-first search (BFS) approach.\n   - In the worst case, where the binary tree is a complete binary tree, there are N/2 nodes at the last level (where N is the total number of nodes in the tree).\n   - Therefore, the while loop will execute approximately N/2 times, resulting in a linear time complexity of O(N).\n\n2. Space Complexity: O(M)\n   - The space complexity depends on the maximum number of nodes present at any level in the binary tree.\n   - In the worst case, the maximum number of nodes in a level is M/2, where M is the maximum number of nodes at any level.\n   - The space used by the queue will be proportional to the maximum number of nodes at a level.\n   - Therefore, the space complexity is O(M).\n\n# Code\n```\nclass Solution {\n    public int maxLevelSum(TreeNode root) {\n        Queue<TreeNode> pq=new LinkedList();\n        if(root==null)return 0;\n        pq.add(root);\n        int max=Integer.MIN_VALUE;\n        int level=1,maxlevel=1;\n        while(!pq.isEmpty()){\n            int s=pq.size();\n            int sum=0;\n            for(int i=0;i<s;i++){\n                TreeNode node=pq.remove();\n                sum+=node.val;\n                if(node.left!=null)pq.add(node.left);\n                if(node.right!=null)pq.add(node.right);\n            }\n           if(sum>max){\n               max=sum;\n               maxlevel=level;\n           }\n          level++;\n        }\n        return maxlevel;\n\n    }\n}\n```
['Tree', 'Breadth-First Search', 'Java']