Free Trees lessonsTrees · Stage 3 · Paths · Step 4

The best path anywhere

Find the path with the largest sum anywhere in the tree, where a path may bend at one node, by returning the best one-sided gain from every subtree. About 22 minutes.

Two different numbers per node

A path may go up from one node, bend at a highest node, and go down on the other side. At each node you can ask two questions. What is the best path that bends here? That is the node plus the best gain from its left plus the best gain from its right.

And what can this node offer its parent? A path to the parent cannot branch, so it can use only one side. That is the node plus the better of its two sides.

Score here: value plus left gain plus right gain.

Report upward: value plus the better side only.

In code

left, right = 5, 3
through = 10 + left + right   # bends: 18
up = 10 + max(left, right)    # one side: 15

Best path sum in the tree 2, -4, 5, 3, 6, 1, -2.

best: 6

The leaves offer themselves: gains 3, 6, 1 and -2. A negative gain is ignored, so -2 offers 0.

Move 1 of 4

Ignore losing sides

A side with a negative gain makes the path smaller, so a path should simply not include it. Treat any gain below zero as zero, which means: stop here on that side.

An empty child gives gain 0. The best answer must be at least one node, so start the best at negative infinity, never at 0, because all values may be negative.

Negative gains: count as 0 - choose not to go that way.

Start best at minus infinity, since every value may be negative.

In code

# drop a negative side
gain = max(value, 0)

Quick check

A node's left gain is 8 and its right gain is 5, and its value is 3. What does it report to its parent?

A11, which is 3 plus the better side, 8
B16, which is 3 plus both sides
C3, only the node itself

Show the answer

11, which is 3 plus the better side, 8. A path going up through the parent cannot use both sides.

Your problem

Binary tree maximum path sum

A path in a binary tree is a sequence of nodes in which each pair of neighbours is joined by an edge, and each node appears at most once. The path need not pass through the root. Its sum is the sum of the node values. Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path.

Example

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

1 ≤ number of nodes ≤ 3,000 · -1,000 ≤ node.val ≤ 1,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.