Binary Tree Max Path Sum LeetCode 124

LeetCode 124 — Binary Tree Maximum Path Sum — gives you the root of a binary tree and asks you to find the maximum path sum of any non-empty path. A path in a binary tree is defined as a sequence of nodes where each pair of adjacent nodes has an edge connecting them. The path does not need to pass through the root, but it must be contiguous — you cannot skip nodes or teleport between branches.

The challenge is that node values can be negative. Unlike problems where you simply sum all positive nodes, a negative subtree might drag down an otherwise good path. You must decide, at each node, whether including a given subtree helps or hurts the total sum. The global maximum might be a single node, a path through two subtrees, or anything in between.

This problem is frequently cited as one of the hardest "easy to state, hard to solve" tree problems on LeetCode because the recursive structure that solves it requires you to think about two separate things simultaneously at every node.

The core difficulty is that a path can start and end at any node — it does not have to pass through the root. This means you cannot simply run a DFS and return the sum of the best downward path from the root. The maximum path might be entirely within the left subtree, entirely within the right subtree, or it might cross through some interior node using both its left and right children as arms.

Negative node values compound the difficulty. If both children of a node have negative subtree sums, the best path through that node is just the node itself — both arms are excluded. If only one child has a positive subtree sum, you take just that arm. You cannot decide this statically; it must be evaluated dynamically at each node during the traversal.

A naive approach might try to enumerate all paths, but that is O(n²) or worse. The elegant O(n) solution requires separating two distinct concepts that are computed at the same node but serve different purposes.

The solution uses post-order DFS (left → right → root), which processes children before their parent. For each node, we recursively compute the max gain from the left subtree and the max gain from the right subtree. The max gain from a subtree is the best single-branch path sum starting at that subtree's root and going downward — either through the left child, the right child, or stopping at the node itself.

The critical trick is clamping negative gains to zero using max(gain, 0). If the left subtree's best single-branch sum is negative, we treat it as zero — meaning we simply do not extend the path into that subtree. This handles all negative-value subtree cases cleanly without special-casing.

Once we have the left gain and right gain for a node, we compute the "through" path: node.val + leftGain + rightGain. This is the best path that uses this node as the topmost point (the bend in the path). We update the global maximum with this value. Then we return node.val + max(leftGain, rightGain) to the parent — the single best arm this node can offer upward.

Understanding why the function returns one value but computes another is the heart of this problem. The function returns node.val + max(leftGain, rightGain) — the single best arm extending downward. This is what the parent uses to build its own path. A parent can only pick one child arm to extend through; picking both would create a fork that cannot continue upward as a single path.

However, at the current node, we know both arms. The path node.val + leftGain + rightGain uses both arms and treats the current node as the top of an arch. This is a valid path — it starts at the bottom of the left subtree, rises through the current node, and descends into the right subtree. It might be the global maximum. We capture it with the maxSum update before returning.

Every node simultaneously plays two roles: it contributes a single arm upward to its parent (the return value), and it is evaluated as the apex of a complete arch path (the global max update). Both computations happen in the same DFS call, making the O(n) solution possible.

The max(gain, 0) clamping idiom is what makes the algorithm robust against negative values. Without it, a subtree with a net negative sum would drag down the path sum, even if the correct answer is to simply exclude that subtree. By returning 0 instead of a negative gain, we signal to the parent: "there is no benefit in extending the path into this subtree."

This handles the case where both children are negative: leftGain = 0, rightGain = 0, and the best path through the current node is just node.val itself. If node.val is also negative, the global max update still registers it — which matters when every node in the tree is negative and the answer is the single least-negative node.

The edge case of an all-negative tree is why the global max must be initialized to negative infinity, not zero. If initialized to zero, a tree like [-3] would incorrectly return 0 instead of -3. The initialization to -infinity (or to the root value) ensures a correct answer even when every valid path has negative sum.

In Python, the global max is stored as a nonlocal variable or as a list of one element to allow mutation inside the nested helper. The helper function gain(node) checks if node is None (returns 0), computes leftGain and rightGain with clamping, updates self.maxSum or the nonlocal variable with node.val + leftGain + rightGain, then returns node.val + max(leftGain, rightGain). The main function initializes maxSum = float('-inf'), calls gain(root), and returns maxSum. Total solution: about 10 lines.

In Java, the global max is stored as an instance variable int maxSum = Integer.MIN_VALUE. The private helper int gain(TreeNode node) returns 0 for null, computes leftGain = Math.max(gain(node.left), 0) and rightGain = Math.max(gain(node.right), 0), updates maxSum = Math.max(maxSum, node.val + leftGain + rightGain), and returns node.val + Math.max(leftGain, rightGain). The public maxPathSum method calls gain(root) and returns maxSum.

Both implementations run in O(n) time since every node is visited exactly once in the DFS. Space complexity is O(h) where h is the height of the tree, due to the recursive call stack. For a balanced tree h = O(log n); for a degenerate (linear) tree h = O(n). There is no iterative version that meaningfully simplifies this problem — the recursive structure maps naturally to the post-order computation.

Diameter of Binary Tree (LeetCode 543) uses the exact same two-role pattern: the helper returns the depth of the longest downward path (for the parent to use), while the global diameter is updated using leftDepth + rightDepth at each node. If you understand LeetCode 124, LeetCode 543 becomes trivial — the only difference is that diameter counts edges (nodes minus one) rather than summing node values.

Binary Tree Problems Guide covers the full family of tree path and traversal problems, showing how post-order DFS is the common thread connecting path sum, diameter, lowest common ancestor, and tree DP problems. The pattern of "return one value upward, update a global with a different computation" appears in at least five hard LeetCode tree problems.

Flatten Binary Tree to Linked List (LeetCode 114), Serialize and Deserialize Binary Tree (LeetCode 297), and the Dynamic Programming guide all connect to this problem family. Understanding how to separate what a recursive function returns from what it computes as a side effect is a transferable skill that unlocks a large class of hard tree problems.