Maximum path sum

Medium

A path may bend once, at its highest node

Problem

Return the maximum path sum in a binary tree (a path may start and end at any nodes).

In simple words

At each node combine the best downward path from each side; the answer is the best node-through path.

The idea

At each node compute the best downward path through its left and right children; the best path bending here is node + both, while the value returned upward is node + the better single side. Separating those two quantities is the whole trick.

The trick

Answer candidate = node + left + right; return value = node + max(left, right).
Clamp negative child contributions to zero — a negative branch is never worth taking.
O(n) with a single postorder pass.

←→stepspaceplay

1/8

Optimal

timeO(n)spaceO(h)

Best = max(left+right).

1let best = 0;2function height(node) {3  if (!node) return 0;4  const l = height(node.left), r = height(node.right);5  best = Math.max(best, l + r);6  return 1 + Math.max(l, r);7}

Input

nodes: 6, 5 edges

Memory

l+r: —

Output

best: —
diameter: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,2,3]
Output:: 6
Explanation:: 2 + 1 + 3 = 6 is the best path.

Example 2

Input:: tree = [-10,9,20,null,null,15,7]
Output:: 42
Explanation:: 15 + 20 + 7 = 42.

Example 3

Input:: tree = [-3]
Output:: -3
Explanation:: A single node path is -3.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.