Return the maximum sum of values along any path from the root down to a leaf in a non-empty binary tree.
maxPathSum(root)
Input format: level-order with x for missing children. Assume at least one
node.
3 11 4 x x 2 1 // → 14 (3 → 11)
5 4 8 11 // → 20 (5 → 4 → 11)
-1 -2 -3 // → -3 (-1 → -2 is -3; -1 → -3 is -4; best is -3)
A root-to-leaf path is a chain of decisions: at each internal node you go left or right, continuing until you hit a node with no children. You want the single best (highest-sum) chain among all available.
For any node, ask: what's the best path sum starting here and ending at a leaf below? If this node is a leaf, the only path is itself — the answer is its own value. If it has children, the best path is this node's value plus whichever child leads to the better continuation — take the larger of the two children's best sums and add this node's value.
This is optimal substructure: the best path through a node is built entirely from the best paths through its children, with nothing needed from elsewhere in the tree.
You could generate every root-to-leaf path, sum each, and take the max. That works, but it stores every full path (potentially one per leaf) instead of just tracking the one number that matters — the best sum so far. The recursive approach folds "take the max" into the traversal itself.
The trap: nodes with exactly one child. If you naively compare "best through left" against "best through right" and one side is missing, treating the missing side as 0 is unsafe — 0 might look better or worse depending on the real values, and it isn't a real path anyway. The safe rule: if a node has only one real child, the path must go through it — no comparison needed. Only compare left versus right when both children genuinely exist.
Every node is visited once to compute its own contribution, so work is proportional to the number of nodes, and recursion memory is bounded by the tree's height.
def max_path_sum(root):
if root.left is None and root.right is None:
return root.val
if root.left is None:
return root.val + max_path_sum(root.right)
if root.right is None:
return root.val + max_path_sum(root.left)
return root.val + max(max_path_sum(root.left), max_path_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.