# Binary Tree Maximum Path Sum

> How to solve Binary Tree Maximum Path Sum: track the best downward chain at each node with post-order tree dynamic programming.

- Difficulty: Hard
- Category: Trees
- Topics: Tree, DFS, Binary Tree, Dynamic Programming
- Published 2026-08-21

## Problem

A path in a binary tree is a sequence of nodes connected by parent-child edges with no repeated node; it need not start at the root or end at a leaf, and it may bend once, going from one child up into a node and back down into the other. Find the largest sum along any path.

**Example.** For a tree with root `-10`, left child `9`, and right child `20` (children `15` and `7`), the best path is `15 → 20 → 7`, summing to `42`; the root is left out because including it would only lower the total.

## Key idea

Checking every possible path directly is wasteful, since paths overlap heavily. Instead, define for each node its best downward contribution: the largest sum starting there and continuing into at most one child, computed bottom-up. That is the node's value plus whichever child's contribution is larger, with a negative contribution clamped to zero, since a subtree should only count when it helps.

While computing this, also evaluate a candidate that lets the path bend at that node: its value plus both children's contributions, each clamped to zero. Track the largest such candidate as the final answer. The value returned to a parent must stay the single-branch version, since a real path cannot pass through a node twice.

## Solution

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;

  function contribution(node: TreeNode | null): number {
    if (node === null) {
      return 0;
    }

    // Clamp negative contributions to zero, since a subtree should only count when it helps.
    const left = Math.max(contribution(node.left), 0);
    const right = Math.max(contribution(node.right), 0);

    // A path bending at this node can use both children at once; only valid as a candidate answer.
    const bentPath = node.val + left + right;
    best = Math.max(best, bentPath);

    // A parent can only extend one branch, so return the better single-branch chain.
    return node.val + Math.max(left, right);
  }

  contribution(root);
  return best;
}
```

## Complexity

- **Time:** O(n). One post-order visit per node.
- **Space:** O(h). The recursion stack, bounded by the tree's height.

## Watch out for

- Clamp negative child contributions to zero, but always include the node's own value, even when negative.
- Return only the single-branch value to the parent; the bent-path value would let a path effectively reuse a node.
- Initialize the running best to a very small value, since the optimal path may be one negative node if every neighbor is worse.

## Pattern

This is a "return one thing, track another" tree dynamic-programming shape: the return value supplies what a parent needs, a single chain, while a side variable accumulates the true answer. The same shape appears in computing the diameter of a binary tree.

---

Canonical URL: https://www.marauderbot.com/questions/binary-tree-maximum-path-sum
