Breadth-First Search
Level Order Sum
easy
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.
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, null, null, 4]
Output: [1, 7, 3, 4]
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.
Solution
class Solution:
def levelSum(self, root: TreeNode) -> List[int]:
if not root:
return []
nodes = []
queue = deque([root])
while queue:
# start of a new level here
level_size = len(queue)
sum_ = 0
# process all nodes in the current level
for i in range(level_size):
node = queue.popleft()
sum_ += node.val
if 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 list
nodes.append(sum_)
return nodes
Test Your Knowledge
Login to take the complexity quiz and track your progress
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.
Space Complexity: O(N) In the worst case, each node is on its own level, so the output list will contain N elements.