53. Max Path Sum in a Pipeline Tree

Problem

Extending the pipeline-config-tree theme (problem 43): each node is a pipeline stage carrying a value, where a positive value is an expected quality contribution and a negative value is a risk/cost. A "path" is any sequence of nodes connected by edges where each node appears at most once — it does NOT need to pass through the root or any particular node. It can go up through a node and back down through a different child (bending at most once, at a single node).

Find the maximum possible sum along any such path. Node values can be negative, and a path must contain at least one node — an empty path is not allowed.

Source: src/53_max_path_sum_pipeline_tree.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None): ...

def max_path_sum(root: TreeNode) -> int: ...

# tree:    1
#         / \
#        2   3
max_path_sum(root)  # -> 6   (path 2 -> 1 -> 3, bending through the root)

# tree: -3
max_path_sum(root)  # -> -3  (a single node is still a valid path)

Step-by-Step Approach

1. Do a post-order DFS (children before parent), since deciding what a node contributes to a path depends on already knowing what each of its children can contribute.
2. For each node, compute the best "downward extension" from each child — the maximum sum obtainable by continuing a path down through that single child. If a child's best downward extension is negative, clamp it to 0, since including a negative contribution is worse than not extending the path into that child at all.
3. The path THROUGH the current node — the one that bends and uses both children at once — has sum node.val + left_gain + right_gain. This is a candidate for the overall answer, so compare it against a running global-best tracked outside the recursion (via nonlocal).
4. Critically, the value RETURNED to the node's own caller can only be a single downward line, since whatever continues the path further up the tree can only pass through one child of the current node, not both. So return node.val + max(left_gain, right_gain) — pick the better single side, not the sum of both.
5. Run the DFS from the root; once it completes, the tracked global-best is the answer. It's tracked separately from the return value specifically because the best bent path (through both children) is a valid complete path in its own right, but it's a dead end for further upward extension — it can't be represented as "the value returned to the parent."

The subtlety worth internalizing: the value returned to the caller (a single downward extension) is different from the value tracked as the global best (which is allowed to bend through both children at once). A path that bends through both children is a legitimate complete path — it's just not one that can be extended any further upward, because a tree node only has one parent edge going up, not two. Runtime is O(n): each node is visited once, doing O(1) work beyond its two recursive calls.

Reference solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_path_sum(root):
    # post-order DFS: returns best single downward extension, tracks bent-path best via nonlocal, O(n) time/O(h) space
    best = float("-inf")

    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        # a negative contribution is worse than contributing nothing -- clamp at 0
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        # the path THROUGH this node (bending through both children) is a candidate for the global best
        best = max(best, node.val + left_gain + right_gain)
        # but what we RETURN upward can only be a single downward line -- pick one side, not both
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return best

Key Functions & Tricks

• nonlocal best — a side channel outside the recursion that tracks the true global answer, separate from what each call returns.
• max(dfs(node.left), 0) — clamps a negative subtree contribution to zero, since skipping a child beats dragging the path down with it.
• node.val + left_gain + right_gain — the bent-through-this-node candidate, compared against best but never returned upward.
• node.val + max(left_gain, right_gain) — the returned value picks only one side, since a path continuing above this node can only go through one child.
• Post-order recursion order — children fully resolved before the parent decides anything, matching the dependency direction of the computation.

How to Recognize This Pattern