Binary Tree Maximum Path Sum

Problem

A path in a binary tree is any sequence of nodes in which each consecutive pair is joined by an edge, and no node appears more than once. A path can start and end at any nodes in the tree — it does not have to pass through the root, and it does not have to reach a leaf. The path sum is the sum of the values of the nodes on the path.

Given the root of a binary tree, return the maximum path sum over all possible non-empty paths.

Note that node values may be negative, so the best path might be a single node.

Examples

Example 1

    1
   / \
  2   3

Input: root = [1,2,3] → Output: 6 The best path is 2 → 1 → 3 with sum 2 + 1 + 3 = 6.

Example 2

   -10
   /  \
  9    20
      /  \
     15   7

Input: root = [-10,9,20,null,null,15,7] → Output: 42 The best path is 15 → 20 → 7 with sum 42; extending up through -10 would lower the total.

Example 3

Input: root = [-3] → Output: -3 The path must be non-empty, so with a single negative node the answer is that node’s value.

Constraints

• The tree has between 1 and 3 × 10⁴ nodes — an O(n²) scan per node is too slow; aim for O(n).
• -1000 <= Node.val <= 1000 — values can be negative, so including every node is not always optimal.

Think about it first

TL;DR

One post-order DFS that returns each node’s best downward gain while updating a global best “peak” value — O(n) time, O(h) space (h = tree height, for the recursion stack).

Approach 1 — Brute force

Every path has a unique highest node (its peak). For every node, compute the best path that peaks there: node.val plus the best downward-only path into each child subtree (clamped at 0, since a negative arm is better skipped). Take the maximum over all nodes. The naive version recomputes the downward helper from scratch at every node.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxPathSum(root: Optional[TreeNode]) -> int:
    def down(node: Optional[TreeNode]) -> int:
        """Best sum of a path that starts at node and goes only downward."""
        if not node:
            return 0
        return node.val + max(0, down(node.left), down(node.right))

    best = float("-inf")

    def visit(node: Optional[TreeNode]) -> None:
        nonlocal best
        if not node:
            return
        peak = node.val + max(0, down(node.left)) + max(0, down(node.right))
        best = max(best, peak)
        visit(node.left)
        visit(node.right)

    visit(root)
    return int(best)

Complexity: O(n²) time — down costs O(subtree size) and is re-run beneath every node (worst case a skewed tree: 1 + 2 + … + n). O(h) space.

Why the constraints rule it out: n = 3 × 10⁴ gives ~9 × 10⁸ node visits in the worst case, far past the time limit.

Approach 2 — One-pass post-order DFS (the classic)

The brute force recomputes down(child) at every level. A post-order traversal (children before parent) already has both children’s downward gains available when the parent runs, so each node’s downward gain is computed once, and the path peaking at that node is evaluated at the same time. Two quantities are tracked per node:

• what we return to the parent: node.val + max(0, leftGain, rightGain) — a parent can extend only one arm;
• what we record globally: node.val + max(0, leftGain) + max(0, rightGain) — the peak itself may join both arms.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxPathSum(root: Optional[TreeNode]) -> int:
    best = float("-inf")

    def gain(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)   # path peaking here
        return node.val + max(left, right)          # best single arm for parent

    gain(root)
    return int(best)

Walkthrough on Example 2, [-10,9,20,null,null,15,7] (the highlighted nodes form the winning path):

graph TD
    A["-10"] --> B["9"]
    A --> C["20"]
    C --> D["15"]
    C --> E["7"]
    classDef path fill:#2f855a,color:#fff,stroke:#276749;
    class C,D,E path;

Final answer: 42 — the 15 → 20 → 7 path, found at its peak node 20.

Complexity: O(n) time — every node is visited exactly once. O(h) space for the recursion stack (O(n) worst case on a skewed tree, O(log n) if balanced).

Common pitfalls

• Forgetting to clamp negative arms to 0. A subtree with negative best gain should contribute nothing, not a penalty; that is what max(0, …) handles.
• Returning both arms to the parent. node.val + left + right is only valid at the peak; a parent extending this node can continue through one child, so return node.val + max(left, right).
• Initializing best = 0. An all-negative tree (Example 3) must return a negative number; start from -inf (or root.val).
• Recursion depth. A skewed tree of 3 × 10⁴ nodes exceeds CPython’s default recursion limit; call sys.setrecursionlimit(10**5) if the judge doesn’t do it for you.

Pattern takeaway

Many “best path in a tree” problems (Diameter of Binary Tree, Longest Univalue Path, this one) share one shape: do a post-order DFS in which each node returns the best single-arm value its parent could extend, and combines both arms locally into a global answer. Whenever the quantity you report upward differs from the quantity you optimize, keep a global (or nonlocal) best and update it inside the recursion.