Binary Tree Maximum Path Sum (LC 124)

Pattern: Tree DFS + Global Best
Difficulty: Hard
Key Concept: At each node, the best path through that node uses the node plus at most one best “chain” from left and one from right; return to parent only a single downward chain (cannot fork upward).

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge; the path does not need to pass through the root.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Input: root — binary tree node references; node values can be negative.
Output: Integer — maximum sum over all valid paths.

Example

       -10
       /  \
      9    20
          /  \
         15   7

Output: 42 (path 15 → 20 → 7).

Edge: Single node with value -3 → output -3 (path must be non-empty).

---

1. Algorithm & Pseudocode

Brute force

1. Enumerate every pair of nodes (or every simple path) by DFS from every possible start, exploring all continuations — O(n³) or O(n²) with heavy duplication.
2. Or: list all root-to-leaf paths and all paths between any two nodes by storing parent pointers and LCA — very heavy implementation and worse constants.

Pseudocode (naive)

best = -infinity
for each node u as path start:
    for each descendant v:
        consider path from u to v (only valid if contiguous in tree — need tree paths)
        best = max(best, sum(path))

// Correct but enumerating all simple paths explicitly is exponential or O(n^2) per start

Optimal

1. DFS post-order; for each node compute:
   • gainLeft = max(0, dfs(node.left)) — extend left only if positive contribution.
   • gainRight = max(0, dfs(node.right)).
2. Path through node: node.val + gainLeft + gainRight — update global best.
3. Return to parent: node.val + max(gainLeft, gainRight) (only one branch can extend upward).

Pseudocode

best = -infinity

function dfs(node):
    if node == null: return 0
    left = max(0, dfs(node.left))
    right = max(0, dfs(node.right))
    best = max(best, node.val + left + right)
    return node.val + max(left, right)

call dfs(root)
return best

---

2. Step-by-Step Analysis (Beginner-Friendly)

• A path is not required to go to a leaf; it can stop early if negatives hurt — handled by max(0, childGain).
• You cannot return left + right + val to the parent because a valid upward path uses at most one child branch plus the current node.
• Global best captures arch-shaped paths (through current node) while return value captures straight chains for ancestors.
• Negative node values force best to track the maximum seen even if all contributions are negative (single-node path).

---

3. The Dry Run

Tree

    -10
    /  \
   9   20
      /  \
     15   7

Assume post-order; dfs returns max single-chain gain to parent (after clipping negatives to 0).

Visit	node.val	left (clipped)	right (clipped)	candidate through node	best after
9	9	0	0	9	9
15	15	0	0	15	15
7	7	0	0	7	15
20	20	15	7	20+15+7=42	42
-10	-10	9	35	-10+9+35=34	42

Returns: dfs(-10) = -10 + max(9, 35) = 25 (not needed for final answer).

ASCII (values in parentheses = returned chain to parent)

        -10  (returns 25 to parent if any; answer is global best 42)
       /   \
      9     20  (through-node 42)
     (9)   /  \
          15   7
         (15) (7)

Path for 42: 15 — 20 — 7.

---

4. Java Solution

Brute Force

Try every node as the highest node on the path: for each node, compute best path entirely in left subtree ending at node.left, best in right ending at node.right, without reusing work — implemented naively with repeated DFS sums.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n^2) worst skewed — repeated subtree sum scans
    // Space: O(h) recursion
    public int maxPathSum(TreeNode root) {
        int[] best = { Integer.MIN_VALUE };
        for (TreeNode n : allNodes(root)) {
            int left = oneSideMax(n.left);
            int right = oneSideMax(n.right);
            best[0] = Math.max(best[0], n.val + Math.max(0, left) + Math.max(0, right));
        }
        return best[0];
    }

    private int oneSideMax(TreeNode node) {
        if (node == null) return 0;
        return node.val + Math.max(0, Math.max(oneSideMax(node.left), oneSideMax(node.right)));
    }

    private Iterable<TreeNode> allNodes(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        dfsCollect(root, list);
        return list;
    }

    private void dfsCollect(TreeNode n, List<TreeNode> list) {
        if (n == null) return;
        list.add(n);
        dfsCollect(n.left, list);
        dfsCollect(n.right, list);
    }
}

Optimal

class Solution {
    private int best;

    // Time: O(n), Space: O(h) stack
    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        dfs(root);
        return best;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

---

5. The “Java vs. Others” Edge

• Use an int[] holder or a class field for best because Java has no nonlocal/out int; a single int[1] works but a private field is common in solutions.
• Integer.MIN_VALUE is the right initial best so a tree of all negatives still picks the least bad single node.
• Avoid Stack; if iterative, use Deque — but recursion is standard here.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (per-node rescan)	O(n²) worst	O(h)	Recomputes one-side max from each node
Optimal DFS	O(n)	O(h)	One post-order pass; global tracks arch paths