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; going up through -10 would only hurt.

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 “take everything” never works.

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). So: 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) — and 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

class Solution:
    def maxPathSum(self, 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 kill it: 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 insight: the brute force recomputes down(child) at every level, but post-order traversal (children before parent — a classical DFS ordering) hands us both children’s downward gains exactly when we need them. So compute each node’s downward gain once, and at that same moment evaluate the path that peaks at this node. Two different quantities live side by side:

• 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

class Solution:
    def maxPathSum(self, 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]:

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 — max(0, …) is the whole trick.
• 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.