## Level Order Sum

###### DESCRIPTION

Given the root of a binary tree, return the sum of the nodes at each level. The output should be a list containing the sum of the nodes at each level.

###### EXAMPLES

**Example 1**:

Input:

`[1, 3, 4, null, 2, 7, null, 8]`

Output: [1, 7, 9, 8]

**Example 2**:

Input:

`[1, 2, 5, 3, null, null, 4]`

Output: [1, 7, 3, 4]

Run your code to see results here

## Explanation

We should recognize that a level-order breadth-first traversal of the binary tree is the most straightforward way to solve this problem.

At each level, we can keep a running sum of the node's values at that level. Then, whenever we finish processing a level (the for-loop for that level finishes), then we can add the sum of the nodes to the output list.

class Solution:def levelSum(self, root: TreeNode) -> List[int]:if not root:return []nodes = []queue = deque([root])while queue:# start of a new level herelevel_size = len(queue)sum_ = 0# process all nodes in the current levelfor i in range(level_size):node = queue.popleft()sum_ += node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)# we are at the end of the level,# add the sum of the nodes to the output listnodes.append(sum_)return nodes

## Complexity Analysis

**Time Complexity:** O(N) where N is the number of nodes in the tree. We visit each node exactly once, and each node, we perform a constant amount of work, so the time complexity is O(N).
**Space Complexity:** O(N). In the worst case, each node is on its own level, so the output list will contain N elements.

Loading comments...