Binary Tree Maximum Path Sum — Solution

Problem

Given a binary tree where each node holds an integer (which can be negative), find the path through the tree with the largest possible sum. A path is any sequence of connected nodes — it doesn't need to start at the root or end at a leaf, and each node may appear at most once.

[-10,9,20,null,null,15,7]

• Input: root = [-10, 9, 20, null, null, 15, 7]
• Output: 42
• Explanation: The path 15 → 20 → 7 arches through node 20 and yields 15 + 20 + 7 = 42.

Counter-example: the path 9 → -10 → 20 is also valid but sums to only 19 — the root's negative value drags it down.

Intuition

At any node, the maximum-sum path that passes through it can extend into the left subtree, the right subtree, both, or be just the node itself. The crucial observation is that when handing a value back to a parent you can only carry one branch upward — a path can't fork. So the global maximum and the value you return are two separate calculations made at every node.

Solution — DFS with Global Max

Post-order DFS: after computing the best gains from both children, calculate the arch value (both branches through the current node), update the global maximum, then return only the best single-direction gain so the parent can extend the path.

1. Recursively compute left_gain from the left child; clamp to 0 if the subtree is a net negative.
2. Recursively compute right_gain from the right child; clamp to 0 if the subtree is a net negative.
3. Update the global maximum with node.val + left_gain + right_gain — the arch through this node.
4. Return node.val + max(left_gain, right_gain) so the parent receives only one branch.

1class Solution:
2    def maxPathSum(self, root: Optional[TreeNode]) -> int:
3        self.global_max = float('-inf')
4
5        def max_gain(node):
6            if not node:
7                return 0
8            left_gain = max(max_gain(node.left), 0)   # discard subtree if it hurts overall sum
9            right_gain = max(max_gain(node.right), 0)
10            self.global_max = max(self.global_max, node.val + left_gain + right_gain)
11            return node.val + max(left_gain, right_gain)  # only one branch goes up to parent
12
13        max_gain(root)
14        return self.global_max

Time: O(n) — each node is visited exactly once during the post-order traversal.
Space: O(h) — the recursion stack reaches a depth equal to the tree's height; O(log n) for a balanced tree and O(n) for a skewed one.

Complexity Summary

Common Mistakes

• Returning the arch value upward — node.val + left_gain + right_gain is correct for updating the global max, but wrong to return to the parent. A path can't fork: the parent can only extend one branch, so you must return node.val + max(left_gain, right_gain).
• Not clamping negative gains to zero — if a subtree has a negative total, including it in the path reduces the sum. Always take max(gain, 0) before adding, so you effectively "cut" the subtree.
• Initializing the global max to 0 — a tree of all negative values (e.g., [-5]) should return -5. Initializing to 0 incorrectly returns 0 because no path that updates the max ever fires.
• Assuming the path must pass through the root — the problem allows any path. In the example the optimal path (42) entirely skips the root (-10).
• Forgetting that a single node is a valid path — max(gain, 0) clamping combined with global_max = max(global_max, node.val + 0 + 0) correctly handles leaf nodes and all-negative subtrees.

Related Problems

• path-sum — simpler path problem where the path must run from root to leaf; good warm-up for understanding tree traversal
• path-sum-ii — collect all root-to-leaf paths that hit a target sum; extends path-sum with backtracking
• path-sum-iii — same arch DFS structure, but counts paths summing to a target that can start and end anywhere
• diameter-of-binary-tree — identical DFS shape: compute left/right depths, update a global max with both, return only one direction upward
• sum-root-to-leaf-numbers — accumulates values top-down along root-to-leaf paths, complementing this problem's bottom-up perspective