C++ | BFS Traversal | Easy to understand | Clean codes | Level order Traversal
Intuition\nAs we have to find the sum of elements at each level and thereby find the level with max sum, we can use a BFS for it.\n Describe your first thoughts
# Intuition\nAs we have to find the sum of elements at each level and thereby find the level with max sum, we can use a BFS for it.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nDo a BFS traversal of the tree and whenever we are at a level sum up all the nodes on that level, after this check if the sum is greater than the maxSum till now and accordingly update the sum and level.\n\nWe maintain the \'ans\' as our final level with maximum sum. \'Sum\' is used to maintain the maximum sum, \'level\' keeps a track of the levels.\n\nIn the BFS traversal we take the size of queue at that instant and run a for loop (this loop covers all nodes at a particular level).\nAfter the loop finishes just check that is the sum at this level is greater than the maximum sum so far, if so, then make the \'Sum\' equal to \'sum\' and our \'ans\' to level. \n\nAt last return the \'ans\'.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n), n is the total number of nodes in the tree.\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n), for queue.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\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) return 0;\n        queue<TreeNode*> q;\n        q.push(root);\n        int ans=1;\n        int Sum=INT_MIN;\n        int level=0;\n        while(!q.empty()){\n            level++;\n            int size=q.size();\n            int sum=0;\n            for(int i=0;i<size;i++){\n                TreeNode* node=q.front();\n                sum+=node->val;\n                if(node->left) q.push(node->left);\n                if(node->right) q.push(node->right);\n                q.pop();\n            }\n            if(sum>Sum){\n                Sum=sum;\n                ans=level;\n            }\n        }\n        return ans;\n    }\n};\n```\n# *Please upvote if this helped!*
['C++']