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, 4]

Output: [1, 7, 3, 4]

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

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

What is the time complexity of this solution?

O(n)

O(log m * n)

O(1)

O(n³)

Mark as read

Next: Rightmost Node