Binary Tree Maximum Path Sum

Medium

Bend at most once, drop negative branches

Problem

Return the maximum path sum in a binary tree (path may bend at a node).

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 the best bending path is node + left + right, while the value handed upward is node + the better single branch, since a parent cannot use both. Clamping negative branch contributions to zero encodes 'just skip that side'.

The trick

Two different quantities: the answer candidate and the return value.
Clamp each child's contribution with max(0, …).
O(n) with one 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.