Command Palette

Search for a command to run...

Hectal
Problem 16.12 · Binary TreesHard

Binary Tree Maximum Path Sum

PatternTree DFSKadane's Algorithm

What it teaches: Kadane's idea on a tree: each node returns its best one-sided gain (ignoring negative branches) and records the best two-sided path.

Practise it on judges as “Binary Tree Maximum Path Sum”.

The problem

A path is any sequence of connected nodes, each used at most once, not necessarily through the root. Return the maximum sum of any non-empty path.

Example 1

Input: root = [1, 2, 3]
Output: 6

Example 2

Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42

15 → 20 → 7.

Constraints

  • 1 ≤ nodes ≤ 3 × 10⁴
  • −1000 ≤ value ≤ 1000

Pattern clues in the wording

  • → Best path anywhere
  • → Negative values: sometimes it's better to leave a branch out

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int maxPathSum(TreeNode root) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
root = [1,2,3]
6
2
root = [-10,9,20,null,null,15,7]
42
3
root = [-3]
-3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Gain with a global best · O(n)
1

Gain with a global best

Time O(n) Space O(h)

gain(n) = n.val + max(0, gain(left), gain(right)) restricted to one side; best = max(best, n.val + max(0, gainL) + max(0, gainR)).

Approach 1
class Solution {
    private int best = Integer.MIN_VALUE;

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

    private int gain(TreeNode n) {
        if (n == null) return 0;
        int l = Math.max(0, gain(n.left));
        int r = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + l + r);     // path bending at n
        return n.val + Math.max(l, r);            // one side only for the parent
    }
}

Verdict: One post-order pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All negative (answer is the largest single node)
  • Single node

Mistakes people make

  • Starting best at 0 (wrong for all-negative trees).
  • Returning both sides to the parent.

Interview

Follow-up questions

How is this like Kadane's algorithm?