BFS Traversal
Intuition\n Describe your first thoughts on how to solve this problem. \nAs to return the maximum sum of each level, its better to use BFS. Can use DFS traversa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs to return the maximum sum of each level, its better to use BFS. Can use DFS traversal too but the solution become a little bit complex.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will traverse each level and store the sum of all the nodes in that level to result(array to store the resultant sum of each level). Ultimately we will find the smallest index having the largest sum.\n\nNote that we are not calculating the height of the binary tree to declare a array of size equal to that if the height.\nIndeed we traverse the tree only once and store the result, each element in the queue contains the node value along with the level the node is present.\n\nModifications:\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n), where n is the number of nodes of Binary tree. We are going to traverse the tree only once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n), we are going to store the nodes in the process queue.\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n        # apply BFS\n        result = []\n        if root == None:\n            return result\n        \n        process = [[root, 1]] # Store the node & level\n        while len(process) > 0:\n            front = process[0]\n            node, level = front[0], front[1]\n            process.pop(0)\n\n            """\n            based on the length -> \n            1. insert node value if level is not added before\n            2. add the value to the corresponding level\n            """\n            if len(result) < level: # new level arrived\n                result.append(node.val)\n            else: # already the nodes in corresponding level is processed so just add to result[corresponding level]\n                result[level - 1] += (node.val)\n\n\n            # insert the nodes in the process\n            if node.left != None:\n                process.append([node.left, level + 1])\n            if node.right != None:\n                process.append([node.right, level + 1])\n            \n        return result.index(max(result)) + 1 # as 1 base indexing\n\n        \n```
['Python3']