BFS Level Order | Python / JS Solution
Hello Tenno Leetcoders, \n\nFor this problem, we are given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.\nWe
Hello **Tenno Leetcoders**, \n\nFor this problem, we are given the `root` of a binary tree, the level of its root is `1`, the level of its children is `2`, and so on.\nWe want to return the `smallest` level `x` such that the sum of all the values of nodes at level `x` is `maximal`.\n\n### Explanation\n\nSince, we want to find the smallest `level` sum such that all values of nodes at that current level is maximal, we can utilize BFS `level order` to calculate the sum at each level.\n\n1. Start by checking if tree is empty, we will return 0 since there will not be any levels to perform level order\n2. Initialize:\n    - A variable `max_sum` to store the maximum sum encountered thus far and set it to negative infinity as we want to find the maximal sum\n    - A variable `max_level` to store the level with the maximum sum starting from 0\n    - A variable `current_level` to keep track of the current level during our queue traversal starting from level 0\n    - Create a queue and put root node to start the level order traversal\n3. Traverse the q until empty and perform the following:\n    - Increment `current_level` by `1` to keep track of the current level\n    - Initialize `current_level_sum` variable to calculate the current level sum node vales and set it to 0\n    - For JavaScript, we want to first store the initial length of the queue before we process nodes at the current level to make sure nodes wont be skipped\n    - Now iterate the length of our q to process all the nodes at the current level and as we iterate:\n        - Dequeue a node from the front of the queue and add its values to current_level_sum\n        - If dequeued node has a left or right child, we will enqueue to the queue\n    - After processing all node at the current level, if our current level sum is greater than our current max sum, this means we have found a level with a larger sum. In this case:\n        - Update the maximum sum accordingly\n        - Set max level to the current level\n4. Return the max level\n\n# Code\n\n**Python**\n\n```\nfrom collections import deque\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\nclass Solution:\n    def maxLevelSum(self, root: Optional[TreeNode]) -> int:\n\n        if not root: return 0\n        max_sum = float("-inf")\n        max_level = 0\n        current_level = 0\n\n        q = deque([root])\n        \n        while q:\n            current_level += 1\n            current_level_sum = 0\n    \n            for _ in range(len(q)):\n                current_node = q.popleft()\n                current_level_sum += current_node.val\n\n                if current_node.left: q.append(current_node.left)\n                if current_node.right: q.append(current_node.right)\n\n            if current_level_sum > max_sum:\n                max_sum = current_level_sum\n                max_level = current_level\n            \n        return  max_level\n```\n\n**JavaScript**\n```\n/**\n * Definition for a binary tree node.\n * function TreeNode(val, left, right) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.left = (left===undefined ? null : left)\n *     this.right = (right===undefined ? null : right)\n * }\n */\n/**\n * @param {TreeNode} root\n * @return {number}\n */\nvar maxLevelSum = function(root) {\n    if(!root) return 0\n    let maxSum = -Infinity\n    let maxLevel = 0, currentLevel = 0\n\n    const q = [root]\n\n    while(q.length) {\n        currentLevel += 1\n        let currentLevelSum = 0\n        const levelSize = q.length\n        for (i = 0; i < levelSize; i++){\n            const currentNode = q.shift()\n            currentLevelSum += currentNode.val\n            if(currentNode.left) q.push(currentNode.left)\n            if(currentNode.right) q.push(currentNode.right)\n        }\n\n        if(currentLevelSum > maxSum){\n            maxSum = currentLevelSum\n            maxLevel = currentLevel\n        }\n    }\n    return maxLevel\n};\n```\n### Time Complexity: `O(n)`\n\n### Space Complexity: `O(m)`\n\nwhere m is the max number of nodes at any level in the binary tree\n\n***Warframe\'s Darvo wants you to upvote this post  \uD83D\uDE4F\uD83C\uDFFB \u2764\uFE0F\u200D\uD83D\uDD25***\n![image](https://assets.leetcode.com/users/images/814f5668-c966-46d7-ba42-e5435c4c1761_1675302761.3081913.gif)
['Breadth-First Search', 'Python3', 'JavaScript']