#1161

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Level Sum of a Binary Tree

Find the level of a binary tree where the sum of its nodes is maximal, with an emphasis on binary-tree traversal.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, the levels are assigned such that the root is at level 1, its children are at level 2, and so on. For each level, the sum of the node values at that level must be calculated.

Your task is to return the level with the maximum sum. If there are multiple levels with the same sum, return the smallest level. This involves binary-tree traversal and state tracking to calculate sums at each level and determine the one with the greatest value.

Examples

Example 1

Input: root = [1,7,0,7,-8,null,null]

Output: 2

Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.

Example 2

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]

Output: 2

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105

Solution Approach

Level-wise traversal

To find the level with the maximum sum, perform a level-order traversal (BFS). Start from the root and move to each level, calculating the sum of nodes at each level. Track the maximum sum encountered and the corresponding level.

Use of state tracking

As you traverse, maintain a record of the current sum at each level. Update the maximum sum and level accordingly. This can be done using a queue to store the nodes at each level during BFS.

Return the level

Once all levels have been processed, return the level corresponding to the maximum sum. If multiple levels have the same sum, return the smallest level number.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because each node in the binary tree is visited exactly once. The space complexity is O(n) due to the need to store nodes in the queue during level-order traversal, where n is the number of nodes in the tree.

What Interviewers Usually Probe

Candidate correctly identifies that BFS is the most suitable approach for level-order traversal.
Candidate demonstrates understanding of state tracking while performing BFS to calculate sums.
Candidate handles multiple levels with the same sum, returning the smallest level.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the case where multiple levels have the same sum and not returning the smallest level.
Incorrectly calculating the sum for each level, leading to the wrong level being returned.
Using an inefficient traversal method like DFS, which may not handle large trees as well as BFS in this case.

Follow-up variants

Modify the problem to return the level with the smallest sum rather than the largest.
Instead of returning the level number, return the sum at the level with the maximum sum.
Handle edge cases with trees that only contain one node, returning level 1.

FAQ

What is the main pattern for solving Maximum Level Sum of a Binary Tree?

The main pattern involves binary-tree traversal and state tracking. Typically, BFS is used to process nodes level by level while calculating their sums.

How do I calculate the sum for each level?

To calculate the sum at each level, perform a BFS traversal and keep track of the nodes at each level, summing their values as you process each level.

What should I do if multiple levels have the same sum?

If multiple levels have the same sum, return the smallest level number as specified in the problem statement.

Can this problem be solved using DFS?

While DFS can be used, BFS is generally more efficient for this problem as it directly processes nodes level by level, which aligns with the problem requirements.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited exactly once during the traversal.

terminal

Solution

Solution 1: BFS

We use BFS to traverse level by level, calculating the sum of nodes at each level, and find the level with the maximum sum. If there are multiple levels with the maximum sum, return the smallest level number.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        mx = -inf
        i = 0
        while q:
            i += 1
            s = 0
            for _ in range(len(q)):
                node = q.popleft()
                s += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if mx < s:
                mx = s
                ans = i
        return ans

Solution 2: DFS

We can also use DFS to solve this problem. We use an array $s$ to store the sum of nodes at each level. The index of the array represents the level, and the value of the array represents the sum of nodes. We use DFS to traverse the binary tree, adding the value of each node to the sum of nodes at the corresponding level. Finally, we return the index corresponding to the maximum value in $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        mx = -inf
        i = 0
        while q:
            i += 1
            s = 0
            for _ in range(len(q)):
                node = q.popleft()
                s += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if mx < s:
                mx = s
                ans = i
        return ans

Continue Practicing

#1123 lowest common ancestor of deepest leaves #1261 find elements in a contaminated binary tree #1302 deepest leaves sum