Binary Tree Maximum Path Sum
Understanding the Problem
We need to find a path in a binary tree that gives the maximum sum. The path can start and end at any node, it does not have to go through the root, and it does not have to go from a leaf to another leaf. The only rule is that the path must follow parent-child edges and cannot visit a node more than once.
A valid path has a specific shape. In a tree, any path looks like an inverted "V" (or a straight line, which is a degenerate case). It goes up from some node to an ancestor, then possibly back down through the other child. So at any node, the path either passes through it as a "bend point" (using both left and right subtrees), or it continues upward through one side only.
Each node therefore involves two separate computations. First, what is the best path that bends at this node (left + node + right)? That is a candidate for the global answer. Second, what is the best path we can report upward to the parent? That can only include one side, because a path cannot fork.
Key Constraints:
1 <= number of nodes <= 3 * 10^4- An O(n^2) algorithm performs around 9 * 10^8 pair computations, too slow for typical limits. We need O(n) or O(n log n).-1000 <= Node.val <= 1000- Node values can be negative, so including a subtree can reduce the sum. The solution must handle the case where the best choice is to skip a subtree entirely.
Approach 1: Brute Force (Enumerate All Paths)
Intuition
Treat every pair of nodes as the endpoints of a path, compute the sum of the path between them, and track the maximum. In a tree, there is exactly one path between any two nodes, so finding it is well-defined.
For each pair of nodes (u, v), the path goes from u up to their lowest common ancestor (LCA), then down to v. We can find the LCA and compute the path sum for each pair.
A path can also be a single node, so every individual node counts as a candidate too.
Algorithm
- Collect all nodes in the tree.
- For every pair of nodes (u, v), find their lowest common ancestor.
- Compute the path sum from u to LCA to v.
- Track the maximum path sum across all pairs.
- Return the maximum.
Example Walkthrough
Input:
All possible paths and their sums: node 1 alone (sum=1), node 2 alone (sum=2), node 3 alone (sum=3), path 2->1 (sum=3), path 1->3 (sum=4), path 2->1->3 (sum=6).
Output:
Code
- Time Complexity: O(n^3). We have O(n^2) pairs of nodes, and for each pair, finding the LCA and computing the path sum each take O(n). So the total is O(n^2) * O(n) = O(n^3).
- Space Complexity: O(n). We store all n nodes in a list, and the recursion stack can go up to O(n) deep for a skewed tree.
At O(n^3), this cannot handle 3 * 10^4 nodes. The optimal solution drops the endpoint-pair view entirely: it treats each node as a potential bend point of the path and computes everything in a single DFS.
Approach 2: DFS with Global Maximum (Optimal)
Intuition
Instead of working with path endpoints, work with the "top" of the path, the node where the path bends. Every path in a tree has exactly one highest node. At that node, the path either goes down into the left subtree, the right subtree, or both.
At each node, compute the best path that has this node as its highest point: best gain from the left child + node's value + best gain from the right child. Compare that "fork" sum against the global maximum. Because every path has exactly one highest node, checking the fork sum at every node considers every path exactly once, at the node where it reaches its highest point.
When reporting a value upward to the parent, we can only go in one direction. A path cannot fork, so we report: node's value + max(left gain, right gain). The parent can then extend this single-branch path further.
One post-order DFS computes both quantities. At each node, we compute the "gain" (the maximum sum achievable going downward from this node along a single branch), update the global answer with the fork sum, and return the single-branch gain to the parent.
One more detail: if a subtree's gain is negative, we clamp it to zero. Extending a path into a subtree that reduces the total sum never helps, so we skip it.
Algorithm
- Initialize a global variable
maxSumto negative infinity. - Define a recursive function
maxGain(node)that returns the maximum gain achievable by going downward fromnodealong a single branch. - For a null node, return 0 (no gain).
- Recursively compute
leftGain = max(maxGain(node.left), 0)andrightGain = max(maxGain(node.right), 0). Clamping to 0 means we skip negative subtrees. - Compute the "fork path" sum:
node.val + leftGain + rightGain. UpdatemaxSumif this is larger. - Return
node.val + max(leftGain, rightGain)to the parent, since we can only extend the path in one direction. - After the DFS completes, return
maxSum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once during the DFS. At each node, we do O(1) work (comparisons and additions). So the total is O(n).
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. For a balanced tree, h = O(log n). For a skewed tree, h = O(n) in the worst case.
The DFS in Approach 2 recurses once per level of the tree, so its stack depth equals the tree height. The constraints allow a skewed tree with 3 * 10^4 nodes, which overflows Python's default recursion limit of 1000 frames and can exhaust thread stacks in other runtimes. An explicit stack removes that risk.
Approach 3: Iterative Post-Order (Explicit Stack)
Intuition
The algorithm is unchanged from Approach 2: every node needs the single-branch gains of its children before it can compute its own fork sum and gain. The recursion produced that children-before-parents ordering implicitly. We can produce the same ordering explicitly in two passes.
Pass 1 builds a list of nodes in which every parent appears before its children. Pop nodes from a stack one at a time, append each popped node to the list, and push its children. A node's children enter the stack only after the node itself has been appended, so they always appear later in the list.
Pass 2 walks that list in reverse, which yields a children-before-parents order. Each node's gain goes into a hash map keyed by node, the fork sum is computed exactly as before, and the global maximum is tracked across all nodes.
This gain-and-fork structure is the general tree DP shape: compute a value per node from its children's values, combine the children's values at each node into a candidate for the global answer, and pass only the restricted single-branch value upward. The same structure solves Diameter of Binary Tree, Longest ZigZag Path in a Binary Tree, and Longest Univalue Path.
Algorithm
- Push the root onto a stack and create an empty list
order. - While the stack is not empty: pop a node, append it to
order, and push its non-null children. After the loop, every parent inorderprecedes its children. - Create an empty map
gainand initializemaxSumto negative infinity. - Iterate
orderfrom the last element to the first. For each node, look upleftGainandrightGainin the map (0 for a missing child), clamping each to at least 0. - Update
maxSumwith the fork sumnode.val + leftGain + rightGain. - Store
gain[node] = node.val + max(leftGain, rightGain). - After the loop, return
maxSum.
Example Walkthrough
Code
- Time Complexity: O(n). Pass 1 pushes and pops each node once. Pass 2 processes each node once with O(1) average-cost map operations.
- Space Complexity: O(n). The order list and the gain map each hold all n nodes, and the explicit stack can hold up to O(n) nodes. Approach 2 uses only O(h) space, so this version trades memory for immunity to call-stack limits.