Dynamic Programming • Trees

Maximum Path Sum in Binary Tree

Find the maximum path sum between ANY two nodes in a binary tree. The path does not need to pass through the root.

Overview

This is DP on Trees. We use a post-order DFS to process children before their parents. At each node, we make decisions based on the max paths coming from its subtrees.

Ignoring Negatives

If a subtree returns a negative sum, it's better to just not include it. We use `Math.max(0, dfs(child))` to "clip" negative branches.

The Global Arc

The highest path sum might arch over the current node, combining both left and right subtrees: `node.val + left + right`. We update `globalMax` with this.

The Return Value

However, when a node returns to its parent, it can only offer ONE path (it can't split). So it returns `node.val + max(left, right)`.

-10

9

20

15

7

Code Tracker

:::

1let globalMax = -Infinity;

2function dfs(node) {

3 if (!node) return 0;

4 let leftMax = Math.max(0, dfs(node.left));

5 let rightMax = Math.max(0, dfs(node.right));

6

7 globalMax = Math.max(globalMax, node.val + leftMax + rightMax);

8

9 return node.val + Math.max(leftMax, rightMax);

10}

Max Path Sum Tree

Max Path Sum Tree

Maximum Path Sum in Binary Tree

Overview

Ignoring Negatives

The Global Arc

The Return Value

Maximum Path Sum in Binary Tree

Overview

Ignoring Negatives

The Global Arc

The Return Value