Binary Tree Maximum Path Sum

Given a binary tree, return the maximum path sum. A path can start and end at any nodes and follows parent-child edges without repeating a node. It may go upward to its highest node and then downward into another branch; it is not restricted to a single downward chain.

Why this is worth learning

A path may join two downward branches at one highest node, but a branch returned to a parent may use only one child. Mixing these two quantities creates a branching object rather than a path.

Before coding: one-minute experiment

At a node valued 10 with child gains 4 and 7, what complete-path candidate is recorded and what gain can be returned to its parent?

Function signature

func MaxPathSum(root *TreeNode) int

Inputs / outputs

• root: root of the tree.
• Return: maximum path sum.

Example

   -10
   /  \
  9   20
     /  \
    15   7
Output: 42 (15 + 20 + 7)

Constraints

• 1 <= number of nodes <= 100_000
• Node values in [-1000, 1000]

Core idea (near-solution)

Enumerating every pair of endpoints would consider many overlapping paths. Instead assign each path to its highest node. At that node it may combine one downward arm from the left and one from the right. But the value returned to a parent can contain only one arm: returning both would create a three-way fork when extended upward. Keep these two roles separate. Discard negative child contributions when combining, yet include the current node so an all-negative tree still has a nonempty answer. The returned node-plus-one-arm gain may itself be negative.

Invariant: the helper returns the best downward path starting at this node.

Algorithm (step-by-step)

1. DFS each node to compute left/right gains.
2. Update global max with node.Val + leftGain + rightGain.
3. Return node.Val + max(leftGain, rightGain) to parent.

Correctness sketch

For each node, let left and right be the best nonnegative gains extending down through one child. Any simple path whose highest node is the current one consists of the node plus at most one branch from each side, so node.Val+left+right is the best such complete path. Every tree path has exactly one highest node, so a global maximum over these candidates considers all paths. A path that will continue to the parent cannot take both child branches, because adding the parent would give degree three at the current node. Return node.Val+max(left,right) as the extendable gain. Initializing the global answer below all node values preserves a nonempty answer for all-negative trees.

Trace (hand walkthrough)

Example input:
   -10
   /  \
  9   20
     /  \
    15   7
Output: 42 (15 + 20 + 7)

Walk:
- Leaf 9: gain=9, global=9.
- Leaf 15: gain=15, global=15.
- Leaf 7: gain=7, global=15.
- Node 20: left=15, right=7, candidate=42 => global=42, gain=35.
- Root -10: left=9, right=35, candidate=34 => global stays 42.

Pitfalls to avoid

• Forgetting to drop negative gains (use max with 0).

Debugging lens

Test all-negative nodes and a best path wholly inside a subtree. The path need not contain the root. A nonempty path may move up to one ancestor and then down another branch.

Complexity

• Time: O(n)
• Extra space: O(h).

Implementation notes (Go)

• Clamp each child contribution before combining. The returned nonempty gain may itself be negative.
• Track the global best path sum as a separate variable.

Reconstruction checkpoint

A tree has root −4 and leaf children −6 and −2. Give each leaf’s returned gain, the root’s returned gain, and the final answer. Which step would make a zero answer incorrect?

Return to Binary Tree General · Module quiz