Breadth first search | Golang | C++ | Python
Intuition\n Describe your first thoughts on how to solve this problem. \nWe have to traverse the tree in such a way that we can have the sum of current level so
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have to traverse the tree in such a way that we can have the sum of current level so, that we can compare our curr_sum with max_sum_so_far. So, this statement clearly gives the sign of breadth first search, we are going to implement BFS here.\n\nIf you don\'t know BFS already!! [Read this](https://cp-algorithms.com/graph/breadth-first-search.html)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nprerequisite for the algorithm are\n`int max_sum_so_far = INT_MIN`\n`int lvl = 0` and\n`int min_lvl_so_far = 0`\n\nNow we, will put each level in a queue and pop them one by one by the size of the queue. This idea help us to traverse the tree by level.\nRest we just have to calculate the current sum and maintain the level.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nwhere n is the number of nodes in the tree.\n\n# Code\n```Go []\n/**\n * Definition for a binary tree node.\n * type TreeNode struct {\n *     Val int\n *     Left *TreeNode\n *     Right *TreeNode\n * }\n */\nfunc maxLevelSum(root *TreeNode) int {\n\tlvl := 0\n\tmin_lvl_so_far := 0\n\tmax_sum_so_far := math.MinInt64\n\tq := []*TreeNode{root}\n\n\tfor len(q) > 0 {\n\t\tlvl++\n\t\tcurrSum := 0\n\t\tn := len(q)\n\n\t\tfor n > 0 {\n\t\t\tnode := q[0]\n\t\t\tq = q[1:]\n\t\t\tcurrSum += node.Val\n\n\t\t\tif node.Left != nil {\n\t\t\t\tq = append(q, node.Left)\n\t\t\t}\n\t\t\tif node.Right != nil {\n\t\t\t\tq = append(q, node.Right)\n\t\t\t}\n\n\t\t\tn--\n\t\t}\n\n\t\tif max_sum_so_far < currSum {\n\t\t\tmax_sum_so_far = currSum\n\t\t\tmin_lvl_so_far = lvl\n\t\t}\n\t}\n\n\treturn min_lvl_so_far\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int maxLevelSum(TreeNode* root) {\n        int lvl = 0, min_level_so_far = 0, max_sum_so_far = INT_MIN;\n        queue<TreeNode*> q;\n        q.push(root);\n\n        while(!q.empty()) {\n            lvl ++;\n            int curr_sum = 0;\n            int n = q.size();\n\n            while(n--) {\n                TreeNode* node = q.front();\n                q.pop();\n                curr_sum += node->val;\n\n                if(node->left) q.push(node->left);\n                if(node->right) q.push(node->right);\n            }\n\n            if(max_sum_so_far < curr_sum) {\n                max_sum_so_far = curr_sum;\n                min_level_so_far = lvl;\n            }\n        }\n\n        return min_level_so_far;\n    }\n};\n```\n```Python3 []\nclass Solution:\n    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n        lvl, min_level_so_far, max_sum_so_far = 0, 0, float(\'-inf\')        \n        q = [root]\n\n        while(len(q) > 0):\n            n = len(q)\n            curr_sum = 0\n            lvl += 1\n\n            while n > 0:\n                n -= 1\n                node = q.pop(0)\n                curr_sum += node.val\n\n                if node.left:\n                    q.append(node.left)\n                if node.right:\n                    q.append(node.right)\n\n            if max_sum_so_far < curr_sum:\n                min_level_so_far = lvl\n                max_sum_so_far = curr_sum\n\n        return min_level_so_far\n```
['Tree', 'Breadth-First Search', 'C++', 'Go', 'Python3']