Binary Tree Maximum Path Sum
The Prompt
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the `root` of a binary tree, return the maximum path sum of any non-empty path.
Understanding the Problem
A path here is any chain of connected nodes — it does not need to touch the root or end at a leaf, and it can bend: go up through a node and back down its other side. You want the maximum possible sum over all such paths.
The tension: a bent path through a node uses BOTH of its children, but that node cannot then extend the path upward to its parent — a path may bend only once. The trick is to track two different quantities per node: the best "gain" it can pass up (node + one child chain), and the best full path that bends at it (node + both child chains), recorded into a global maximum.
The Interview Flow
Interviewer
This is a challenging problem. How do you find the maximum path sum in a binary tree, where the path can start and end anywhere?
Candidate
This smells like a recursive DFS approach. For each node, I need to make a decision. The maximum path could pass through this node, or it could be entirely contained within its left or right subtrees.
Interviewer
What information does a recursive call need to return to its parent?
Candidate
A parent node needs to know the maximum path sum that *starts* at its child and goes downwards. A path can only go up and then down once. So a child can't return a path sum that includes both its left and right children to its parent. It can only return a straight path down.
Interviewer
So, for a node, what does its recursive function return?
Candidate
The function will return `node.val + max(left_path_sum, right_path_sum)`. And crucially, if a subtree path sum is negative, we shouldn't include it, so we take `max(0, ...)`.
Interviewer
But where do you calculate the final answer? The returned value is only for paths extending upwards.
Candidate
Right. I need a global or a reference variable to store the overall maximum path sum found so far. Inside the recursive function for a given node, after I get the max downward paths from my left and right children, I can calculate a potential new maximum path that is "split" at the current node. This path sum would be `node.val + left_path + right_path`. I compare this value with my global maximum and update it if necessary. Then, I return the maximum downward path as we discussed.
Interviewer
That's the complete logic. It correctly distinguishes between the value to be returned and the value used to update the global maximum. Please implement it.
Why does one DFS handle paths that bend anywhere?
The invariant: gain(node) returns the maximum sum of a downward chain starting at node — node.val plus the better of its children's gains, clamped at 0 because a negative chain is better dropped entirely. Every optimal path bends at exactly one node; when DFS processes that node, node.val + leftGain + rightGain is exactly that path's sum, and the global max captures it. Since every node is considered as the bend point, no path is missed.
One post-order pass, O(1) work per node: O(n) time and O(h) recursion space. The clamp max(gain, 0) is the detail interviewers probe — it is how negative subtrees are excluded without special cases.
Recursive DFS with a Global Maximum
- Initialize a global variable `maxSum` to negative infinity.
- Define a recursive helper function `dfs(node)`.
- **Inside `dfs(node)`:**
- Base case: if `node` is null, return 0.
- Recursively call `dfs` on the left and right children. Important: Clamp the returned values at 0, since we don't want to include paths with a negative sum. `leftMax = max(0, dfs(node.left))`, `rightMax = max(0, dfs(node.right))`.
- Calculate the potential maximum path sum that includes the current node as the "root" of the path (the split point). This is `node.val + leftMax + rightMax`. Update the global `maxSum` with this value if it's greater.
- The function must return the maximum path sum that can extend *upwards* to its parent. This path cannot include both left and right children. So, return `node.val + max(leftMax, rightMax)`.
- Call `dfs(root)` to start the process.
- Return the global `maxSum`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (!node) return 0;
const leftMax = Math.max(0, dfs(node.left));
const rightMax = Math.max(0, dfs(node.right));
// Update maxSum with path that includes the current node as the root
maxSum = Math.max(maxSum, node.val + leftMax + rightMax);
// Return max path sum that can extend upwards
return node.val + Math.max(leftMax, rightMax);
}
dfs(root);
return maxSum;
}Explanation
Find the maximum path sum in [−10, 9, 20, 15, 7] — gains flow up while bent paths are scored at each node.
1Leaves first: each leaf's upward gain is its own value (9, 15, 7 — all positive, so none is clamped to 0).
2At 20: the bent path 15 → 20 → 7 sums to 15 + 20 + 7 = 42 — global best so far. Upward, 20 may keep only one arm: gain = 20 + max(15, 7) = 35.
3At the root: the bent path through −10 is 9 + (−10) + 35 = 34, which does not beat 42. The answer stays 42, from the path 15 → 20 → 7 that never touches the root.
Complexity Analysis
TIME
O(n)
SPACE
O(h)
Finished working through this one?
Mark it complete to track it on your Data Structures path.