TL;DR
Level-order BFS, summing one level per queue drain — O(n) time, O(w) space (w = max width).
Approach 1 — Brute force: one full traversal per level
First find the tree’s height H, then for each level 1..H traverse the
whole tree again, summing only the nodes at that depth.
# 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
def maxLevelSum(root: Optional[TreeNode]) -> int:
def height(node: Optional[TreeNode]) -> int:
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
def level_sum(node: Optional[TreeNode], level: int) -> int:
if not node:
return 0
if level == 1:
return node.val
return (level_sum(node.left, level - 1)
+ level_sum(node.right, level - 1))
best_level, best_sum = 1, level_sum(root, 1)
for lvl in range(2, height(root) + 1):
s = level_sum(root, lvl)
if s > best_sum:
best_sum, best_level = s, lvl
return best_level
Complexity: O(n · h) time, O(h) space. On a skewed tree of 10^4 nodes that
is about 10^8 node visits, which is why the intended solution computes all
level sums in a single pass.
Approach 2 — BFS level by level (the classic)
Breadth-first search visits the tree one level at a time. Record the queue
length before draining, and one while iteration processes exactly one level,
so its sum is ready when the level ends. Track the best sum and the first level
that achieves it.
# 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
from collections import deque
def maxLevelSum(root: Optional[TreeNode]) -> int:
queue = deque([root])
best_sum = root.val
best_level = 1
level = 0
while queue:
level += 1
level_total = 0
for _ in range(len(queue)):
node = queue.popleft()
level_total += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level_total > best_sum:
best_sum = level_total
best_level = level
return best_level
The tree for root = [1,7,0,7,-8,null,null], with its three levels:
graph TD
A[1] --> B[7]
A --> C[0]
B --> D[7]
B --> E[-8]
Walkthrough on root = [1,7,0,7,-8,null,null]:
- Level 1: queue
[1] → total 1; best = (1, level 1). Enqueue 7, 0.
- Level 2: drain
[7, 0] → total 7 > 1; best = (7, level 2). Enqueue 7, -8.
- Level 3: drain
[7, -8] → total −1; not better. Queue empty → return 2.
Complexity: O(n) time — each node enqueued and dequeued once; O(w) space where
w is the maximum level width (up to n/2 on a complete tree).
The strict > in the comparison is what implements “smallest level wins ties”.
Approach 3 — DFS with depth-indexed sums (the well-known alternative)
BFS grouping isn’t required; any traversal works as long as each visit knows
its depth. Recurse carrying depth, accumulate into a list where index d
holds level d+1’s running sum, then scan for the first maximum.
# 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
def maxLevelSum(root: Optional[TreeNode]) -> int:
sums: List[int] = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
if not node:
return
if depth == len(sums):
sums.append(node.val)
else:
sums[depth] += node.val
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
best = max(sums)
return sums.index(best) + 1
Walkthrough on root = [-1,-2,-3]: visit -1 at depth 0 → sums = [-1];
-2 at depth 1 → sums = [-1, -2]; -3 at depth 1 → sums = [-1, -5].
max is -1, first at index 0 → return 1.
Complexity: O(n) time, O(h) recursion stack plus O(h) for sums (one entry
per level). On a deep skewed tree this recursion can hit Python’s default
limit (~1000), so BFS is the safer production choice; on a wide bushy tree,
DFS’s O(h) beats BFS’s O(w) memory. Choose the traversal whose memory profile
fits the tree shape.
Common pitfalls
- Returning as soon as a level sum decreases — negative values mean sums can
dip and then recover, so every level must be examined.
- Initializing
best_sum = 0 — an all-negative tree then reports the wrong
level. Seed it from the root (or use -inf).
- Using
>= when updating the best, which breaks the tie toward deeper
levels; the problem wants the smallest level.
- Forgetting that levels are 1-indexed in the answer while your list or
counter is 0-indexed.
Pattern takeaway
Level-based questions are a natural fit for BFS. Anything phrased in terms of
levels — level sums, level averages, rightmost node per level, zigzag order —
maps to the same loop that snapshots the queue length before draining it. DFS
carrying a depth parameter is the interchangeable alternative whenever
recursion depth is safe. Choose between them by memory: O(width) for BFS,
O(height) for DFS.