Binary Tree Maximum Path Sum

Hints

1. Classify paths by their topmost node. Every path has exactly one node closest to the root. Grouping candidate paths by that node means each path is considered exactly once, and it turns "search all paths" into "visit every node once".
2. Name the two shapes. At node X the best path topping out there is an arch: left arm, plus X, plus right arm. The thing X can contribute to a parent is an arm: X plus its better side only. Two different numbers, computed in the same call.
3. Return the arm, record the arch. The recursive return value must be node.val + max(left_arm, right_arm). The arch node.val + left_arm + right_arm goes into a running global maximum and is never returned. Conflating these is the defining bug of this problem.
4. Clamp negative arms to zero. If a subtree's best arm is negative, attaching it strictly lowers the sum, so decline it. max(dfs(child), 0) expresses "take this arm only if it helps". Zero means "attach nothing", which is always available because the path may stop at this node.
5. Initialise the global to negative infinity, not zero. Every value can be negative, and the path must be non-empty. On [-3] the answer is -3. A global seeded at 0 reports 0, which corresponds to the empty path the problem forbids.
6. Update at every node, not just the root. The second example's answer sits entirely inside the right subtree. Any solution that only measures the arch at the root returns -10 + 9 + 20 = 19 instead of 42.

Solution

Approach 1 - Enumerate every path: O(n^2) time or worse

Worth sketching only to see why the structure matters.

def max_path_sum_brute(root):
    best = float('-inf')
    nodes = []

    def collect(n):
        if n:
            nodes.append(n)
            collect(n.left)
            collect(n.right)
    collect(root)

    def arm(n):                      # best downward arm from n
        if n is None:
            return 0
        return n.val + max(arm(n.left), arm(n.right), 0)

    for n in nodes:                  # n as the topmost node of the path
        left = max(arm(n.left), 0)
        right = max(arm(n.right), 0)
        best = max(best, n.val + left + right)
    return best

This is correct and it recomputes arm from scratch for every node. On a balanced tree the repeated work sums to O(n log n); on a degenerate spine it reaches O(n^2). The fix is not a different algorithm but a different traversal order: compute each arm once, bottom-up, and use it on the way back. That observation collapses the whole thing into one post-order pass. It is worth pausing on the structure of the waste, because it recurs. Every call to arm on a node recomputes the arms of that node's entire subtree, and those same arms were already computed when the loop visited each of those descendants in turn. Nothing about the values changes between visits; only the order of computation is wrong. Whenever a recursive helper is called from inside a loop over all nodes, ask whether the loop can be folded into the recursion so each value is produced once and consumed on the way back up. The answer is usually yes, and it is usually the difference between a quadratic solution and a linear one.

Approach 2 - Post-order, return the arm and record the arch: O(n) time, O(h) space

The answer. One traversal, two quantities.

import math

def max_path_sum(root):
    best = -math.inf

    def dfs(node):
        nonlocal best
        if node is None:
            return 0                       # attaching nothing contributes nothing

        left  = max(dfs(node.left), 0)     # decline a negative arm
        right = max(dfs(node.right), 0)

        best = max(best, node.val + left + right)   # arch: recorded, not returned
        return node.val + max(left, right)          # arm: returned, not recorded

    dfs(root)
    return best

Why the arm cannot include both children: the value returned to a parent will be extended by that parent, so it must have a free end. A node plus both of its subtrees has no free end; joining it to a parent produces a degree-three vertex, which is a fork rather than a path. Returning the arch therefore yields sums for shapes that are not paths, and the reported answer exceeds the true maximum. This is the error that makes solutions pass the first example, where the arch happens to top out at the root, and fail the second.

Why clamping at zero is correct and not a heuristic: the path is allowed to stop at the current node, so declining a subtree is always a legal option worth exactly 0. If the best arm from a child is negative, taking it produces a strictly smaller sum than declining it, so the optimum never includes it. max(gain, 0) is therefore an exact statement of the choice, not an approximation. Note this is also why the null case returns 0: an absent child is the same as a declined one.

Why the global must be seeded below every possible value: all node values can be negative, and a path must contain at least one node, so the answer can be as low as -1000. Seeding the global at 0 silently encodes the empty path, which the statement forbids, and returns 0 on any all-negative tree. Note the clamping is on the arms, never on the node's own value: node.val always enters the arch, which is what keeps single-node paths reachable.

Why one pass suffices: each node is visited once and does constant work beyond its two recursive calls, so the total is O(n). The arch at each node is computed from arms that are already final, because post-order guarantees both children are fully processed before the parent runs. Classifying every path by its topmost node means the n arches examined cover every possible path exactly once, so nothing is missed despite the algorithm never enumerating paths explicitly.

Why space is O(h): the recursion stack holds one frame per node on the current root-to-node path. Balanced trees give O(log n); a 3 * 10^4-node spine gives O(n) frames and exceeds CPython's default recursion limit, so an explicit stack is the production answer. The nonlocal keyword is required because best is assigned inside the nested function; without it Python creates a fresh local each call and the global never accumulates.

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

The winning arch, 42, is recorded at node 20 and never travels upward. Node 20 hands its parent only 35, the single better arm. The root's own arch is 34, which loses. This table is the clearest demonstration that the returned value and the recorded value must differ.

Complexity comparison

Edge cases to verify

• Single node, negative: [-3] returns -3. Catches a global seeded at 0.
• All negative: [-2, -1, -3] returns -1, the least-bad single node. Both arms are declined.
• Best path avoids the root: [-10, 9, 20, null, null, 15, 7] returns 42. Catches recording the arch only at the root.
• One negative child: [2, -1] returns 2. Catches a missing clamp.
• Left spine of 3 * 10^4 nodes: valid input, deep enough to exhaust the default recursion limit.

Where beginners go wrong

• Returning the arch instead of the arm. The defining error. return node.val + left + right hands the parent a shape with no free end, so extending it produces a fork rather than a path. The reported maximum is too large and corresponds to a structure the problem does not permit.
• Recording the arch only at the root. The best path frequently lives entirely inside one subtree. Every node is the top of some candidate path, so the global must be updated in every call.
• Forgetting to clamp negative arms. Without max(gain, 0), a negative subtree drags down every path that passes through its parent. The path is allowed to stop, so declining an arm is always available and always at least as good as taking a negative one.
• Clamping the node's own value. The clamp belongs on the arms, never on node.val. Clamping the node itself makes all-negative trees return 0, which is the empty path the statement forbids.
• Initialising the global to 0. Same symptom, different cause. On [-3] the answer is -3. Seed with negative infinity, or with the root's value.
• Forgetting nonlocal. In Python, assigning to best inside dfs creates a fresh local on each call unless declared nonlocal. The outer variable keeps its seed and the function returns negative infinity. Using a one-element list is the older workaround and still works.

Interview follow-ups to expect

• "Return the path, not just the sum." Store, at each node, which arm won, then reconstruct by walking down from the node where the best arch was recorded. Keep a reference to that node when the global updates. O(n) time, O(h) extra.
• "Restrict paths to leaf-to-leaf." Only record the arch when both children exist, and return negative infinity rather than 0 from null children so a missing side cannot be silently treated as a valid endpoint. A small change that alters which candidates are legal.
• "The tree is 30000 nodes deep." Convert to an explicit-stack post-order traversal, or run an iterative two-pass scheme that computes arms bottom-up using a stack of visited nodes. Same complexity, no recursion limit.
• "Generalise to an n-ary tree." The arch becomes the node plus its two largest non-negative child arms, so sort or take the top two in a single scan. The arm returned is still the node plus its single best child.
• "What about a general graph instead of a tree?" The longest path problem is NP-hard on general graphs. The tree structure is what makes a linear solution possible, because each node has exactly one parent and so paths decompose uniquely. Being able to say this is a strong answer.
• "Maximum path product instead of sum." Negatives flip signs, so track both the maximum and minimum arm at each node, as with maximum product subarray. The clamping rule no longer applies, since a large negative arm can become the best choice when multiplied by another negative.

Related reading

• Trees: the module this belongs to, including why post-order is the traversal for problems that aggregate upward.
• Validate Binary Search Tree: the complementary pattern, where information flows downward as inherited bounds rather than upward as returned values.
• Recursion as Induction: how to state a recursive contract precisely enough that "return the arm, record the arch" becomes obvious rather than clever.