Binary Tree Maximum Path Sum: the two-path trick that makes O(N) possible

The path in this problem does not have to go through the root, does not have to go from leaf to leaf, and can bend — meaning a node can be the apex of a path that descends into both its left and right subtrees. That last point is the trap. A normal DFS computes one value per node and returns it upward. Here you need two values per node simultaneously: what you return to your parent (a single downward arm), and what you record for the global answer (possibly a bent path you can never extend further). Conflating those two things produces wrong answers every time.

The constraints set the stage. n is up to 3 * 10^4, so O(N^2) is tight and O(N^3) is completely off the table. Node values span [-1000, 1000], which means negative values are common — you can have a perfectly balanced tree where the optimal path is a single leaf node. The problem guarantees at least one node, so initializing the global max to negative infinity and returning it is always safe.

The problem

Given the root of a binary tree, find the maximum path sum across any non-empty path — where a path is any sequence of nodes connected by edges, each node appears at most once, and the path does not need to pass through the root or go from leaf to leaf. Full statement: LeetCode 124.

Constraints:
- The number of nodes in the tree is in the range [1, 3 * 10^4].
- -1000 <= Node.val <= 1000

Why the obvious approach fails

The most literal reading of "try all paths" would be: enumerate every pair of nodes (or every node as a potential apex), compute the path sum through that node, and track the maximum. That is O(N^3) in the worst case — O(N) apex candidates, O(N) to compute the best left arm from each, O(N) to compute the best right arm. Even at n = 10^4 this is 10^12 operations. Not happening.

A somewhat smarter brute force collects all nodes, and for each node runs two DFS calls — one into the left subtree, one into the right — to find the best arm lengths, then combines them. This is still O(N^2) because you repeat the arm-finding work at every node without memoizing anything.

Here is the brute-force skeleton in both languages, written out so the redundancy is visible:

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.result = float('-inf')
 
        def best_arm(node: Optional[TreeNode]) -> int:
            """Return the longest single-arm path starting at node, going downward."""
            if not node:
                return 0
            left = max(0, best_arm(node.left))
            right = max(0, best_arm(node.right))
            return node.val + max(left, right)
 
        def check_all(node: Optional[TreeNode]) -> None:
            """For every node, recompute both arms from scratch and record the bent path."""
            if not node:
                return
            left = max(0, best_arm(node.left))
            right = max(0, best_arm(node.right))
            self.result = max(self.result, node.val + left + right)
            check_all(node.left)
            check_all(node.right)
 
        check_all(root)
        return self.result

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    private int result = int.MinValue;
 
    private int BestArm(TreeNode node) {
        if (node == null) return 0;
        int left = Math.Max(0, BestArm(node.left));
        int right = Math.Max(0, BestArm(node.right));
        return node.val + Math.Max(left, right);
    }
 
    private void CheckAll(TreeNode node) {
        if (node == null) return;
        int left = Math.Max(0, BestArm(node.left));
        int right = Math.Max(0, BestArm(node.right));
        result = Math.Max(result, node.val + left + right);
        CheckAll(node.left);
        CheckAll(node.right);
    }
 
    public int MaxPathSum(TreeNode root) {
        result = int.MinValue;
        CheckAll(root);
        return result;
    }
}

CheckAll visits every node: O(N). At each node it calls BestArm for both children, each of which recurses over the entire subtree below: O(N) per call. Total: O(N^2). For n = 3 * 10^4 that is roughly 9 * 10^8 operations — borderline at best, and the constant is not small because Python recursion is slow. This will TLE on LeetCode.

The waste is obvious once you see it: BestArm for the left child at node X recomputes the same arm values that BestArm for the left child at X's parent will also recompute. You are doing redundant subtree traversals at every level.

H is tree height — O(log N) for balanced, O(N) for a degenerate chain.

The key insight: merge both computations into one pass

The fix is to do the arm computation and the global update in the same DFS call, simultaneously. Here is the precise decomposition:

At every node, define two values:

1. The arm value — the best path that starts at this node and goes straight down into one subtree (or stops here). This is what you return to your parent. A parent can only extend one arm downward, not both — otherwise it would bypass itself and lose the path's contiguity.

2. The apex value — the best path for which this node is the highest point. It can use both the left arm and the right arm, since the path bends here and never needs to go further up.

The apex value gets folded into the global maximum. The arm value gets returned to the caller. You never return the apex value — it would be wrong to do so, because no parent can extend a bent path any further.

Walk through [-10, 9, 20, null, null, 15, 7] by hand, post-order (leaves first):

Node 15 (leaf):

• Left arm = 0, right arm = 0 (no children)
• Apex value = 0 + 15 + 0 = 15. Global max becomes 15.
• Return arm = 15.

Node 7 (leaf):

• Left arm = 0, right arm = 0.
• Apex value = 7. Global max stays 15.
• Return arm = 7.

Node 20:

• Left arm from child = max(0, 15) = 15. Right arm from child = max(0, 7) = 7.
• Apex value = 15 + 20 + 7 = 42. Global max becomes 42.
• Return arm = 20 + max(15, 7) = 35. (Choose the better downward arm, not both.)

Node 9 (leaf):

• Apex value = 9. Global max stays 42.
• Return arm = 9.

Node -10 (root):

• Left arm = max(0, 9) = 9. Right arm = max(0, 35) = 35.
• Apex value = 9 + (-10) + 35 = 34. Global max stays 42.
• Return arm = -10 + max(9, 35) = 25. (Irrelevant — nobody uses this value.)

Answer: 42 (the path 15 -> 20 -> 7).

The optimal DFS post-order solution

from typing import Optional
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')
 
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            # Clip negative contributions: a bad subtree is worth 0, not its negative sum
            left_gain = max(0, dfs(node.left))
            right_gain = max(0, dfs(node.right))
 
            # This node as the apex of a bent path — update global max
            self.max_sum = max(self.max_sum, node.val + left_gain + right_gain)
 
            # Return the best single arm to the parent
            return node.val + max(left_gain, right_gain)
 
        dfs(root)
        return self.max_sum

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}
 
public class Solution {
    private int maxSum;
 
    public int MaxPathSum(TreeNode root) {
        maxSum = int.MinValue;
        Dfs(root);
        return maxSum;
    }
 
    private int Dfs(TreeNode node) {
        if (node == null) return 0;
 
        int leftGain = Math.Max(0, Dfs(node.left));
        int rightGain = Math.Max(0, Dfs(node.right));
 
        // Candidate bent path through this node
        maxSum = Math.Max(maxSum, node.val + leftGain + rightGain);
 
        // Return only the best single arm upward
        return node.val + Math.Max(leftGain, rightGain);
    }
}

Every node is visited exactly once. At each node, work is O(1). Total: O(N) time, O(H) space for the call stack.

Why max(0, ...) on the child gains is safe

This is the greedy move that people sometimes worry about. If the best left subtree arm is negative, you set left_gain = 0. You are pretending the left subtree does not exist for this apex calculation. That is correct because including a negative arm strictly decreases any sum — you are always better off stopping at the current node than continuing into a subtree that drags the sum down.

The path definition allows stopping at any node, so "just this node" is a valid path. max(0, child_gain) is shorthand for "include this child's arm if and only if it helps."

Edge cases that deserve attention

Single node (root = [5]): dfs is called with a leaf. Both left_gain and right_gain are 0 (null children return 0). Apex = 5. Global max = 5. Return arm = 5. Output: 5. Correct — the only path is the single node.

All negative values (root = [-3, -1, -2]): initializing max_sum = float('-inf') (Python) or int.MinValue (C#) is critical. The problem guarantees the path is non-empty, so the answer must be some node value, even if every value is negative. If you initialize to 0 you will return 0 for an all-negative tree, which is wrong. At each node, max_gain = max(0, child_gain) means the children contribute nothing, so every apex = node.val. The global max ends up being the least-negative value in the tree.

Path that skips the root: Example 2 ([-10, 9, 20, null, null, 15, 7]) demonstrates this. The answer (42) is recorded when processing node 20, not the root. The global max variable captures answers that arise anywhere in the tree, not just at the root level.

Degenerate chain (worst-case stack depth): a chain of 3 * 10^4 nodes. The recursion stack hits depth 3 * 10^4. Python's default limit is 1000, so you would need sys.setrecursionlimit(40000) to be safe in a real environment (LeetCode's judge typically sets a higher limit). C# has a much larger default stack and handles this fine.

Path is a single downward arm (root = [1, 2, 3] but left subtree is [2, 10, -5]): the algorithm considers the apex at each node; if the best apex anywhere is a node that uses only one arm, right_gain or left_gain is 0 and the apex equals node.val + one_arm. The bent-path formula degrades correctly to a straight arm.

What I'd ship, and why

I'd ship the single-pass DFS without hesitation. The brute-force version is useful only as a correctness oracle for testing — you run both on random trees and compare outputs during development. In production or an interview, the two-pass O(N^2) version buys nothing and risks TLE.

The only wrinkle in the DFS is the global mutable state. In Python I use self.max_sum on the class instance; in C# I use a field on Solution. If you dislike that, you can pass an array of length 1 as a mutable container, or use a return tuple — but every alternative is less readable than the field approach and conveys no additional information.

The mental model to carry forward: "what do I return vs what do I record". The function returns the arm value (single direction, useful to parent). It records the apex value (bent path, useful only at this node, never sent upward). Every tree problem that involves a global optimum over non-root paths uses some version of this split.

Comparison table

Where this fits in the trees series and what comes next

This is problem 14 in the trees series. By this point you have seen DFS recursion (Maximum Depth, Invert Binary Tree, Same Tree), BFS (Level Order Traversal), and subtree problems (Subtree of Another Tree, Validate BST). The new thing here is the global-max-over-subtree pattern: the answer lives at some interior node you discover mid-DFS, not at the root. That pattern appears in several harder tree problems.

Diameter of Binary Tree (543) is the closest sibling. Replace "max path sum" with "max path length in edges." The structure is identical: at each node, combine left and right depths for the apex value, return one depth to the parent. If this problem clicked, 543 will feel like a template.

Longest Univalue Path (687) adds a constraint: the path must consist of nodes with the same value. The arm-or-zero decision becomes "extend into child only if child value equals current value." Same two-return-values pattern, tighter extension rule.

Path Sum III (437) asks for the count of paths summing to a target, allowing paths that start and end anywhere. It uses prefix sums with a hash map rather than post-order DP, so the technique is different — but the "paths need not pass through root" setup is the same.

Count Good Nodes in Binary Tree (1448) threads a "max seen so far" value down through DFS — a different direction of information flow (top-down rather than bottom-up), which is a useful counterpoint to internalize alongside the bottom-up pattern here.