☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Maximum path sum

Medium TUF ID 132 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A path in a binary tree is a sequence of nodes where each consecutive pair is joined by an edge and no node appears twice. The path does not need to pass through the root and may start and end at any node, but it must contain at least one node. The path sum is the sum of the node values on it. Given the root of a non-empty binary tree, return the maximum path sum.

Constraints: 1 ≤ n ≤ 3 × 10^4 nodes, -1000 ≤ value ≤ 1000. The largest possible absolute sum is 3 × 10^7, so int arithmetic is safe.

Example 1

tree (level order) = [1, 2, 3]

     1
    / \
   2   3

answer = 6          // 2 -> 1 -> 3

Example 2

tree (level order) = [-10, 9, 20, null, null, 15, 7]

    -10
    /  \
   9    20
       /  \
      15   7

answer = 42         // 15 -> 20 -> 7; adding the root (-10) and 9 would only give 34

As with the diameter, every path has a unique highest node. From there it goes down along at most one branch on the left and at most one branch on the right. So the best path whose highest node is v equals v.val plus the best downward path starting at v.left (or nothing, if that is negative) plus the same on the right. The answer is the maximum of that over all nodes v. Two differences from the diameter make this problem harder: values can be negative, so sometimes a side should be dropped, and the path must contain at least one node, so an all-negative tree must return its largest single value rather than 0.

Approach 1: Brute force

Intuition. Define maxDown(v): the best sum of a path that starts at v and only goes downward, possibly stopping right at v. It is v.val plus the better of the two children’s maxDown, or plus nothing if both are negative. Then treat every node as the highest point of the path and combine its two sides, clipping each side at 0. Each maxDown call walks a whole subtree, which makes this quadratic.

Algorithm.

  1. maxDown(null) = 0; maxDown(v) = v.val + max(0, maxDown(left), maxDown(right)).
  2. For every node v: candidate = v.val + max(0, maxDown(left)) + max(0, maxDown(right)).
  3. Return the largest candidate.
static int maxDown(TreeNode node) {
    if (node == null) return 0;
    int bestChild = Math.max(maxDown(node.left), maxDown(node.right));
    return node.val + Math.max(bestChild, 0);
}

static int bruteForce(TreeNode root) {
    int best = root.val + Math.max(0, maxDown(root.left)) + Math.max(0, maxDown(root.right));
    if (root.left != null) best = Math.max(best, bruteForce(root.left));
    if (root.right != null) best = Math.max(best, bruteForce(root.right));
    return best;
}

Complexity. Time O(n^2) in the worst case, for example a chain, where maxDown is recomputed from every node down. Space O(h) for the recursion.

Approach 2: Optimal, one post-order pass

Intuition. Compute maxDown for every node bottom-up in a single post-order traversal, exactly as the diameter problem computes heights. When a node has its children’s results in hand, it does two different jobs:

Clipping at 0 is where negative values are handled: a subtree whose best downward sum is negative only hurts, so we act as if we did not enter it. Note that the node’s own value is never clipped, which is exactly what makes the “at least one node” rule work: an all-negative tree still records its single best node.

Algorithm.

  1. best = Integer.MIN_VALUE.
  2. gain(null) = 0.
  3. For a node: left = max(0, gain(node.left)), right = max(0, gain(node.right)).
  4. best = max(best, node.val + left + right).
  5. Return node.val + max(left, right).
  6. The answer is best after calling gain(root).
static int optimal(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    gain(root, best);
    return best[0];
}

static int gain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Math.max(0, gain(node.left, best));     // a negative branch is better dropped
    int right = Math.max(0, gain(node.right, best));
    best[0] = Math.max(best[0], node.val + left + right);  // path bending here uses both sides
    return node.val + Math.max(left, right);               // the parent can extend only one side
}

Dry run on Example 2 (nodes in the order the post-order finishes them):

node left gain right gain bending sum best after returns
9 0 0 9 9 9
15 0 0 15 15 15
7 0 0 7 15 7
20 15 7 42 42 35
-10 9 35 34 42 25

The root’s bending sum is 34, worse than the 42 found at node 20, so the answer is 42.

Complexity. Time O(n): each node is visited once with constant work. Space O(h) for the recursion.

Why it is correct. For every node v, gain(v) returns the true maxDown(v). That holds for leaves, and by induction the clipped children’s gains are the best non-negative extensions on each side. The best path with highest node v is therefore exactly the node.val + left + right computed at v, and since every path has some highest node and every node is visited, the maximum over all of them is the answer.

Edge cases and pitfalls