🔥Only thing you need to know is bfs 🔥| ✅ Beginner Friendly (Explained step by step)✅
Intuition\nThe intuition behind the solution is to perform a breadth-first search (BFS) traversal of the binary tree and keep track of the level of each node. B
# Intuition\nThe intuition behind the solution is to perform a breadth-first search (BFS) traversal of the binary tree and keep track of the level of each node. By calculating the sum of node values at each level and comparing it with the maximum sum encountered so far, we can determine the smallest level with the maximum sum.\n\n# Approach\n- The approach involves using a queue to perform BFS. We start by initializing the maximum level and maximum sum with the root\'s level and value, respectively. We enqueue the root node along with its level (which is initially 1) into the queue.\n\n- Then, we enter a while loop that continues until the queue becomes empty. In each iteration, we process the nodes at the current level. We keep track of the size of the queue at the beginning of the loop to ensure we process all nodes at the current level before moving to the next level.\n\n- For each node, we calculate the sum of its value and update the sum variable. We also enqueue its left and right child nodes (if they exist) along with their corresponding levels (current level + 1).\n\n- After processing all nodes at the current level, we compare the sum with the maximum sum encountered so far. If the sum is greater, we update the maximum sum and set the maximum level to the current level.\n\n- Finally, we increment the level counter and continue with the next level until the queue becomes empty.\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is O(N), where N is the number of nodes in the binary tree. This is because we need to visit each node once during the BFS traversal.\n\n\n\n- Space complexity:\nThe space complexity is O(M), where M is the maximum number of nodes at any level in the binary tree. In the worst case, the last level of the binary tree can contain N/2 nodes, so the space complexity is O(N/2), which simplifies to O(N) in the asymptotic analysis.\n# Code\n```\n// #include <queue>\n// #include <utility>\n\n// struct TreeNode {\n//     int val;\n//     TreeNode* left;\n//     TreeNode* right;\n//     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n//     TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}\n// };\n\nclass Solution {\npublic:\n    int maxLevelSum(TreeNode* root) {\n        if (root == nullptr) {\n            return 0;\n        }\n        \n        int maxLevel = 1; \n        int maxSum = root->val;\n        \n        std::queue<std::pair<TreeNode*, int>> q;\n        q.push({root, 1});\n        \n        int level = 1;\n        while (!q.empty()) {\n            int size = q.size();\n            int sum = 0;\n            \n            for (int i = 0; i < size; i++) {\n                TreeNode* node = q.front().first;\n                int currLevel = q.front().second;\n                q.pop();\n                \n                sum += node->val;\n                \n                if (node->left != nullptr) {\n                    q.push({node->left, currLevel + 1});\n                }\n                if (node->right != nullptr) {\n                    q.push({node->right, currLevel + 1});\n                }\n            }\n            \n            if (sum > maxSum) {\n                maxSum = sum;\n                maxLevel = level;\n            }\n            \n            level++;\n        }\n        \n        return maxLevel;\n    }\n};\n\n```
['Breadth-First Search', 'Queue', 'C++']