Binary Tree Maximum Path Sum — DFS with Returning Branch Gains
Compute the best downward gain from each node while tracking the maximum path that can pass through the node.
Problem Statement
Given a non-empty binary tree, find the path with the largest sum. The path may start and end at any nodes and must follow parent-child connections.
Why This Problem Matters
- Combines recursion with global state tracking.
- Illustrates how to differentiate between paths you can propagate upward versus paths evaluated locally.
- Common interview favourite for demonstrating tree DP reasoning.
Thought Process
Return best downward gain
When recursion returns to parent, only one branch can be extended upward—take the max of left or right gain plus node value, bounded below by zero.
Update global maximum with split paths
Consider paths that use both left and right children plus current node; update a global answer with that sum.
Clamp negative contributions
If a child contributes a negative gain, drop it (treat as zero) so it does not reduce the path sum.
Step-by-Step Reasoning
- Initialise globalMax to Integer.MIN_VALUE.
- DFS returns max downward path sum for each node.
- At node, compute leftGain = max(0, dfs(left)), rightGain = max(0, dfs(right)).
- Update globalMax with leftGain + rightGain + node.val and return node.val + max(leftGain, rightGain).
Dry Run
Tree [-10,9,20,null,null,15,7]
Global max updated to 42 via path 15 → 20 → 7.
Single-node tree [2]
Global max becomes 2; returns 2 as well.
Complexity Analysis
Time
O(n)
Space
O(h)
Why
Each node visited once; recursion depth h equals tree height.
Annotated Solution
public class BinaryTreeMaximumPathSum {
private int best;
public int maxPathSum(TreeNode root) {
best = Integer.MIN_VALUE;
dfs(root);
return best;
}
private int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
best = Math.max(best, left + right + node.val);
return node.val + Math.max(left, right);
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
}DFS returns the best single-branch sum for parent use while updating a global answer with split paths through the current node.
Common Pitfalls
- Forgetting to clamp negative gains causes paths to shrink unnecessarily.
- Returning the split path sum upward leads to double counting; only one branch may extend to parent.
- Global maximum must be initialised low enough to handle all-negative trees.
Follow-Up Questions
- How would you return the actual path nodes?
- Can you adapt the approach if edge weights differ from node values?