124. Binary Tree Maximum Path Sum

At a Glance

• Topic: trees
• Pattern: Tree DFS / DP on Trees
• Difficulty: Hard
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 124

Problem (one-liner)

Given a binary tree with integer node values (may be negative), return the maximum sum of any path that is a simple path (visits no node more than once). A path can start/end anywhere; it need not go through the root.

Recognition Cues

• “Maximum path sum in tree” with negative weights
• At each node: best path may use left + root + right (arch) or extend up to parent (single branch)
• Result is global max of “arch at node” during post-order

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — enumerate every root-to-leaf and every path via brute DFS path lists — exponential time / heavy bookkeeping.
• Acceptable — compute all-pairs path sums via repeated DFS from each node — O(n²) worst on skew trees (still polynomial, wrong asymptotic target).
• Optimal — single post-order pass: return best downward chain (may drop negative child); global answer accumulates node.val + max(0, left) + max(0, right) as candidate “arch” — O(n) time / O(h) stack.

Optimal Solution

Go

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	best := math.MinInt64
	var maxDownward func(node *TreeNode) int
	maxDownward = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		leftGain := maxDownward(node.Left)
		if leftGain < 0 {
			leftGain = 0
		}
		rightGain := maxDownward(node.Right)
		if rightGain < 0 {
			rightGain = 0
		}
		throughNode := node.Val + leftGain + rightGain
		if throughNode > best {
			best = throughNode
		}
		chain := node.Val
		if leftGain > rightGain {
			chain += leftGain
		} else {
			chain += rightGain
		}
		return chain
	}
	maxDownward(root)
	return best
}

JavaScript

function maxPathSum(root) {
	let best = -Infinity;
	function maxDownward(node) {
		if (node === null) {
			return 0;
		}
		const leftGain = Math.max(0, maxDownward(node.left));
		const rightGain = Math.max(0, maxDownward(node.right));
		const throughNode = node.val + leftGain + rightGain;
		if (throughNode > best) {
			best = throughNode;
		}
		return node.val + Math.max(leftGain, rightGain);
	}
	maxDownward(root);
	return best;
}

Walkthrough

Tree [-10,9,20,null,null,15,7] — best path is 15→20→7 sum 42.

At node 20, arch = 20+15+7.

Invariant: maxDownward returns the best upward chain for parent; best captures any V-shaped path at this node.

Edge Cases

• All negative — pick largest single node (gains zeroed from children)
• Skewed tree
• INT_MIN children — use max(0, child) to drop losing branches

Pitfalls

• Returning left+node+right to parent (invalid — path would repeat node)
• Forgetting best can be entirely in subtree below (handled by arch updates)

Similar Problems

• 543. Diameter of Binary Tree — count-based path through any node (Medium stepping stone).
• 113. Path Sum II — all root-to-leaf target sums (Medium; paths from root only).
• 297. Serialize and Deserialize Binary Tree — different tree Hard (structure).

Variants

• Path must go through root — take maxPathSum(root) with extra constraint (simpler).
• Largest BST subtree (LC 333) — different DP state on tree.
• N-ary tree — child list; same arch vs chain idea with max/second max of child contributions.

Mind-Map Tags

#tree-dp #max-path #post-order #negative-weights #arch-vs-chain #global-best