Binary Tree Maximum Path Sum: Global Max with Local Returns

You are given the root of a binary tree where each node contains an integer value (possibly negative). A path is any sequence of nodes where each pair of adjacent nodes has an edge connecting them. The path does not need to pass through the root, and it does not need to start or end at a leaf. Find the maximum sum of any such path.

This is LeetCode 124: Binary Tree Maximum Path Sum, and it uses the same core trick you may have seen in Diameter of Binary Tree: return one thing to the parent, but update a different thing globally. The difference is that instead of counting edges, you are summing node values, and you need to handle negative numbers by dropping branches that would hurt the total.

Why this problem matters

If you have already solved Diameter of Binary Tree, you know the global-max-with-local-return pattern. The recursive function returns depth to the parent but checks left + right against a global max at every node. Binary Tree Maximum Path Sum is the same structural pattern, but with two added twists:

1. You are summing node values, not counting edges. Every node's value contributes to the path sum.
2. Negative branches should be dropped. If a child subtree contributes a negative sum, you are better off not including it at all. This is where max(0, child) comes in.

These two differences make the problem harder to reason about at first, but the skeleton is identical to diameter of binary tree. Once you see the connection, the solution writes itself.

The key insight

At any node, you make two separate decisions:

Decision 1: What is the best path that passes through this node? That path might use the left branch, the right branch, both, or neither. It is node.val + max(0, left) + max(0, right). You check this against the global max. This value never gets returned to the parent because a path that forks at this node cannot be extended further upward.

Decision 2: What is the best single-branch contribution this node can offer to its parent? The parent needs a chain going straight down, not a fork. So you return node.val + max(0, max(left, right)). You pick the better child (or no child if both are negative) and add the current node's value.

The max(0, ...) is the key detail. If a child subtree has a negative best path, you drop it entirely. Including a negative branch would only reduce your total.

The solution

def max_path_sum(root):
    best = float("-inf")

    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    dfs(root)
    return best

Let's walk through each piece:

• best = float("-inf") initializes the global max. You use negative infinity instead of 0 because all node values could be negative. The answer might be a single negative node.
• if node is None: return 0 is the base case. A null node contributes nothing. This is the same recursive null base case you see in every tree problem.
• left = max(0, dfs(node.left)) gets the best single-branch sum from the left subtree, but floors it at 0. If the left subtree would contribute a negative value, drop it.
• right = max(0, dfs(node.right)) does the same for the right subtree.
• best = max(best, node.val + left + right) is the global update. The path through this node uses both branches (each already floored at 0) plus the node itself. If this beats the current best, update it.
• return node.val + max(left, right) is the local return. Tell the parent "the best single-branch contribution through me is my value plus the better of my two children."

Visual walkthrough

Let's trace the recursion through the tree [-10, 9, 20, null, null, 15, 7] step by step. At every node, pay attention to two numbers: what it returns to the parent (single-branch contribution) and what it contributes to the global max (both-branch candidate).

The key moment is Step 4. At node 20, left = 15 and right = 7. The candidate is 20 + 15 + 7 = 42. That becomes the global max. When we return to the root in Step 5, the root's candidate is -10 + 9 + 35 = 34, which does not beat 42. The max path never passes through the root.

Notice how the max(0, ...) clamping did not come into play here because all children had positive contributions. But if node 9 were replaced with -100, its contribution would be clamped to 0, and the root's candidate would be -10 + 0 + 35 = 25. Negative branches get dropped automatically.

Why max(0, child) matters

Consider what happens without the max(0, ...) clamping. If a subtree has a best path sum of -5, including it would subtract 5 from your total. You would be dragging down a perfectly good path by attaching a negative branch to it.

The fix is simple: if a child's contribution is negative, treat it as 0. That is equivalent to saying "do not extend the path into that subtree at all." The path can start and end at any node, so there is no requirement to include any particular branch.

This same logic is why best starts at negative infinity. In a tree where every node is negative, the answer is the single node with the largest (least negative) value. The max(0, ...) will zero out both children at every node, so the candidate at each node is just node.val + 0 + 0 = node.val. The global max picks the least negative one.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work: two comparisons, an addition, and a max update.

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree, h = n.

No extra data structures needed. Just recursion plus one variable to track the global best.

Edge cases to watch for

• All negative values: the answer is the single node with the largest value. The max(0, ...) clamping drops all children, and each node's candidate is just its own value. best starts at negative infinity so it correctly picks the least negative node.
• Single node: the answer is that node's value. Both children are null, so left = 0, right = 0, and the candidate is node.val.
• Path through root: works naturally. If the root's candidate (node.val + left + right) is the largest, the global max captures it.
• Path not through root: also works naturally. The global max is checked at every node, not just the root. The best path might be entirely inside a subtree, as in the example above where the path 15 -> 20 -> 7 never touches the root.
• Single branch path (no fork): if one child is negative, max(0, ...) drops it. The candidate becomes node.val + good_child + 0. The path goes straight down one side.

The building blocks

This problem is built on two fundamental building blocks:

1. Post-order DFS with global state (post-order-global-state). The recursive function processes children before the current node (post-order), returns a local value to the parent, and updates a global variable at each node. The skeleton:

def solve(root):
    best = INIT

    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        best = max(best, CANDIDATE(node, left, right))
        return LOCAL_RETURN(node, left, right)

    dfs(root)
    return best

For max path sum, INIT is -inf, CANDIDATE is node.val + max(0, left) + max(0, right), and LOCAL_RETURN is node.val + max(0, max(left, right)). For diameter of binary tree, INIT is 0, CANDIDATE is left + right, and LOCAL_RETURN is 1 + max(left, right). Same skeleton, different fill-ins.

2. Clamping with max(0, child) to drop negative branches (clamp-negative-branch). When a subtree's contribution is negative, you replace it with 0, effectively choosing not to extend the path into that subtree. This shows up anywhere you need to "take it or leave it" at each branch. The same idea appears in Kadane's algorithm for maximum subarray, where you reset the running sum to 0 whenever it goes negative.

Together, these two building blocks give you the full solution. The post-order global state pattern handles the "return vs. update" split, and the negative branch clamping handles the "include or skip" decision at each child.

From understanding to recall

You just traced through the recursion and watched node 20 produce the winning candidate of 42 while only returning 35 to its parent. You understand why max(0, child) drops negative branches and why best starts at negative infinity. The two-decision structure (global candidate vs. local return) makes sense right now.

But when this problem comes up in an interview, will you remember to initialize best to negative infinity instead of 0? Will you remember that the global update uses left + right while the return uses max(left, right)? Will you remember to clamp children at 0 before using them?

Understanding is not recall. You understood the solution. Recall means you can produce it from scratch under pressure, without mixing up which formula goes where.

Spaced repetition builds recall. You practice typing the solution from memory at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the global max update and the local single-branch return from scratch. After a few repetitions, the pattern is automatic.

The post-order-global-state pattern and the clamp-negative-branch pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Diameter of Binary Tree - The same global-max-with-local-return pattern, but counting edges instead of summing values. Solve this one first if you have not already.
• Path Sum - A simpler tree path problem that passes state downward instead of collecting it upward. Good for seeing the other direction of tree recursion.