59.Binary Tree Maximum Path Sum

HardBlind 75Trees · 14/15

Problem

A path in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge, and no node appears more than once. A path does not have to pass through the root, and it must contain at least one node.

The path sum is the sum of the node values on the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Examples

Input:  root = [1,2,3]
Output: 6
Explanation: The path 2 -> 1 -> 3 has sum 2 + 1 + 3 = 6.

Input:  root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The path 15 -> 20 -> 7 has sum 42. Including -10 would only lower it.

Input:  root = [-3]
Output: -3
Explanation: The path must contain at least one node, so the answer can be negative.

Constraints

The number of nodes in the tree is in the range [1, 3 * 10^4].
-1000 <= Node.val <= 1000

💡 Key Insight

Every path has one highest node where it can bend, taking at most one downward branch on each side. Define gain(node) = the best sum of a path that starts at node and goes straight down (one branch only). The best path bending at node is node.val + max(0, gain(left)) + max(0, gain(right)) — negative branches are dropped. A single post-order DFS computes gain bottom-up and updates the global answer at each node, giving O(n).

Brute Force (Recompute Gains per Node)

TimeO(n²)SpaceO(h)

Intuition

Try every node as the bend point. For each, separately compute the best downward path from its left child and from its right child (clamping negatives to 0), and combine. The downward-gain helper is recomputed from scratch for every candidate, which repeats a lot of work.

Algorithm

gain(node): 0 for null; else node.val + max(0, gain(left), gain(right)).
Traverse every node; for each compute node.val + max(0, gain(node.left)) + max(0, gain(node.right)) and keep the maximum.
Return the maximum.

Visualization

root = [-10,9,20,null,null,15,7]

bend at -10: -10 + 9 + max(0, 20 + 15) = 34
bend at 9  :   9 + 0 + 0               = 9
bend at 20 :  20 + 15 + 7              = 42   <- best
bend at 15 :  15
bend at 7  :   7

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        // best path that bends at root
        int through = root.val
            + Math.max(0, gain(root.left))
            + Math.max(0, gain(root.right));
        int best = Math.max(maxPathSum(root.left), maxPathSum(root.right));
        return Math.max(through, best);
    }

    // best sum of a path starting at node and going down a single branch
    private int gain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int down = Math.max(gain(node.left), gain(node.right));
        return node.val + Math.max(0, down);
    }
}

Complexity

Time: O(n²) — gain costs O(subtree size) and is called for every node; a skewed tree sums to O(n²).
Space: O(h) — recursion depth.

Single Post-Order DFSOptimal

TimeO(n)SpaceO(h)

Intuition

Merge the two recursions. A post-order DFS returns gain(node) to its parent, and at the moment it has both children's gains it also evaluates the path that bends at this node and updates a global best. Key distinction:

What we record at a node may use both branches: node.val + leftGain + rightGain.
What we return to the parent may use only one branch: node.val + max(leftGain, rightGain) — otherwise the parent would get a path that forks.

Clamping child gains at 0 means "don't take that branch if it hurts".

Algorithm

best = Integer.MIN_VALUE.
dfs(node):
- If node is 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.

Dry Run

flowchart TD
    A["-10<br/>left 9, right 35<br/>bend = 34, best stays 42<br/>returns 25"] --> B["9<br/>bend = 9, best = 9<br/>returns 9"]
    A --> C["20<br/>left 15, right 7<br/>bend = 42, best = 42<br/>returns 35"]
    C --> D["15<br/>bend = 15, best = 15<br/>returns 15"]
    C --> E["7<br/>bend = 7<br/>returns 7"]

Post-order visits 9, 15, 7, 20, -10. The best bend is at 20 (15 + 20 + 7 = 42); the root only returns a single branch (-10 + 35 = 25) to its (non-existent) parent.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int best = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return best;
    }

    // returns the best downward (single-branch) path sum starting at node
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, dfs(node.left));   // drop negative branches
        int right = Math.max(0, dfs(node.right));
        best = Math.max(best, node.val + left + right); // path bending here
        return node.val + Math.max(left, right);        // parent may extend one side
    }
}

Complexity

Time: O(n) — each node is visited exactly once.
Space: O(h) — recursion depth; O(n) for a skewed tree.

Complexity Comparison

Approach	Time	Space
Brute Force (Recompute Gains per Node)	O(n²)	O(h)
Single Post-Order DFS	O(n)	O(h)

Common Pitfalls

Initialising best to 0 — for an all-negative tree like [-3] the answer is negative, so start from Integer.MIN_VALUE (or root.val).
Returning node.val + left + right to the parent — that creates a forked "path" which is not allowed.
Forgetting to clamp child gains at 0, so a negative subtree drags a good path down.
Clamping the node's own value at 0 — the path must contain at least one node, and the bending node is always included.