Tree Path Sum
The Intuition
A surprising number of tree problems share one shape: every node decides two things at once. First, the best path that bends at this node and uses both subtrees, which becomes a candidate for the global answer. Second, the best contribution this subtree can pass up to its parent, which can use only one child because a path through the parent can only enter via one side.
Post-order DFS is the right tool. Each recursive call returns the upward contribution. Inside the call, before returning, you combine the two child contributions and update a global best. Returning is not the same as recording the answer.
The clipping rule keeps things tight. If a child returns a negative gain, including it in an upward path makes the path worse, so clip it to zero before adding to the parent's value. The global update can still combine both children, including zeros, because the bend captures the option of using neither side.
Once this template is in place, many "find the best path in a tree" questions become small variants. Maximum path sum is the canonical version. Tree diameter is the same template with depth replacing value. Path sum equals target shifts the question to a depth-first walk that maintains a running remainder and a path stack instead of tracking a global maximum.
The pattern transfers to non-tree DAGs that have unique paths between nodes, and the post-order recursion form is also the foundation of tree DP.
Best path in a tree, longest path, path sum equals target, sum of all paths, tree diameter, problems where each node combines results from its children before answering globally.
- The graph has cycles (tree assumption fails)
- The path can revisit nodes (use Dijkstra or DP on graphs)
- You need every path enumerated for a large tree (too many paths)
Variations:
- Path bend at node: Combine both children for global update; return only the better child for upward extension.
- Strict root-to-leaf: No bending. Carry the running remainder down and check at leaves.
- Path with state: Carry additional info such as last value used, parity, or running XOR to support stricter constraints.
- Counting paths: Replace the max with a sum or count and the same recursion shape applies.
- single node tree
- all negative values (the best path is the largest single node)
- path that is a single node when both children give negative gain
- very skewed trees (recursion depth equals node count)
Key Points
- •Use post-order DFS so each node sees results from its children before deciding
- •Each call returns the best contribution that can extend upward through this node
- •A separate global variable tracks the best path that bends at this node
- •Negative children should be clipped to 0 when extending upward but not when bending
- •The return value and the global update are different quantities
Code Template
1 class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7 def max_path_sum(root):
8 """Maximum sum on any path between two nodes (path may bend at any node)."""
9 best = float('-inf')
10
11 def gain(node):
12 nonlocal best
13 if not node:
14 return 0
15 left = max(gain(node.left), 0)
16 right = max(gain(node.right), 0)
17 # Path that bends at this node uses both children.
18 best = max(best, node.val + left + right)
19 # Path that extends upward through this node picks the better child.
20 return node.val + max(left, right)
21
22 gain(root)
23 return best
24
25 def root_to_leaf_paths_summing_to(root, target):
26 """All root-to-leaf paths whose values sum to target."""
27 paths = []
28
29 def dfs(node, remaining, path):
30 if not node:
31 return
32 path.append(node.val)
33 if not node.left and not node.right and remaining == node.val:
34 paths.append(path.copy())
35 dfs(node.left, remaining - node.val, path)
36 dfs(node.right, remaining - node.val, path)
37 path.pop()
38
39 dfs(root, target, [])
40 return paths
41
42 def diameter(root):
43 """Longest path between any two nodes, measured in edges."""
44 best = 0
45
46 def depth(node):
47 nonlocal best
48 if not node:
49 return 0
50 l = depth(node.left)
51 r = depth(node.right)
52 best = max(best, l + r)
53 return 1 + max(l, r)
54
55 depth(root)
56 return bestCommon Mistakes
- Using the same value for both the return and the global best
- Forgetting to clip negative subtree gains when extending upward
- Mutating the path list without popping (state leaks across siblings)
- Iterative versions that lose the post-order property