Example 1
ready- Input
root = [ 3, 9, 20, null, null, 15, 7 ]- Expected
[ 3, 29, 22 ]- Why
- the three depths sum to 3, 29, and 22
Level Order Sum
25 min · levelOrderSum()easy
An org chart tells a clearer story when you total one row at a time: the director, then every manager, then every person reporting below them.
Given the root of a binary tree, return one sum for each depth — the number of edges
from the root to a node. Entry i in your answer must contain the sum of every node at
depth i; the root sits at depth 0.
A few ground rules:
- Keep the sums ordered from the root downward.
- Include negative values exactly as they are.
- An empty tree has no depths, so return
[].
Constraints
0 <= node count <= 10_000-1_000 <= node.val <= 1_000- Every level sum fits in a signed 32-bit integer.
Hints
Tag each depth
A depth-first walk can carry the current depth beside every node. Grow a sums array when you reach a depth for the first time, then add the node's value to that bucket.
Process a whole row
A queue visits nodes in level order. Before processing a level, save the queue's current length — that many nodes belong to the same sum.
Don't mix the next level in
Children enter the back of the queue while you read the current level. Process only the saved number of nodes before appending the sum.
Follow-up
Could you produce the same sums with depth-first traversal? Which tree shape makes that version hold the most pending work?
Visible cases
Examples
Example 2
ready- Input
root = []- Expected
[]- Why
- an empty tree has no level sums
Example 3
ready- Input
root = [ 1 ]- Expected
[ 1 ]- Why
- the root is the only value at depth 0
Interview signal
Asked at
AmazonGoogle
Depth-tagged DFS — give every value a bucket
A depth-first search (DFS) follows one branch before returning to another. Carry each node's depth on a stack, a last-in, first-out collection, and use that depth as the index of its sum bucket.
def level_order_sum(root: TreeNode | None) -> list[int]:
if root is None:
return []
sums: list[int] = []
stack: list[tuple[TreeNode, int]] = [(root, 0)]
while stack:
node, depth = stack.pop()
if depth == len(sums):
sums.append(0)
sums[depth] += node.val
if node.right is not None:
stack.append((node.right, depth + 1))
if node.left is not None:
stack.append((node.left, depth + 1))
return sumsEvery node contributes once. If h is the tree's number of levels, the result and the
pending DFS path each use at most one slot per level.
Time O(n) — visit each node once. Space O(h) — the buckets and DFS stack grow with the tree's height.
Level-order queue — sum one level at a time
The named pattern is breadth-first level-order traversal (BFS): visit every node at
one depth before moving down, using a queue, a first-in, first-out collection. The
level-size trick means saving len(queue) before the inner loop; that snapshot marks
exactly the nodes in the current level.
from collections import deque
def level_order_sum(root: TreeNode | None) -> list[int]:
if root is None:
return []
sums: list[int] = []
queue = deque([root])
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
sums.append(level_sum)
return sumsChildren join behind the current level, so they can't leak into its sum. If w is the
largest number of nodes on one level, the queue holds O(w) nodes and the answer holds
O(h) sums.
Time O(n) — each node enters and leaves the queue once. Space O(w + h) — the widest pending level plus the returned sums.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 3, 29, 22 ]
Run: visible + custom · Submit: full suite