Return the sum of all values in a binary tree. The empty tree sums to 0.
treeSum(root)
Input format: level-order with x for missing children.
3 9 20 x x 15 7 // → 54
1 2 3 // → 6
(empty) // → 0
This is the same self-similar shape as nearly every tree problem: the sum of the whole tree is defined entirely in terms of a node's own value and the sums of its two subtrees — no need to think about the tree as a whole.
Pick any node and ask: if I already knew the sum of my left subtree and my right subtree, could I produce the sum for my own subtree? Yes — add my own value to both. That's the entire algorithm; the rest is trusting the recursive calls answer the same question correctly for smaller subtrees.
An empty subtree sums to 0. That's what makes a leaf work without special-casing: a leaf's children are both empty, so its total is its own value plus 0 plus 0 — exactly its own value.
You could pass a running total down and mutate it as you go, the way you might in a loop. It's doable, but it fights the natural shape of the problem — a tree has no single obvious visiting order for accumulation, and passing mutable state around adds bookkeeping for no benefit. Having each call simply return its own subtree's sum, and letting the parent combine the two returned values, keeps every call self-contained.
Since you're not tracking a maximum or filtering anything, negative values are just numbers to add — the recursion doesn't care about sign. A tree that sums to zero because positives and negatives cancel out needs no extra logic, which is why "sum" problems are usually simpler than "max" or "count matching" on the same tree shape.
Each node contributes once, so work is proportional to the number of nodes, and the recursion's memory use is bounded by the tree's height.
def tree_sum(root):
if root is None:
return 0
return root.val + tree_sum(root.left) + tree_sum(root.right)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.