We want to find the biggest sum of values along any path in a tree, where a path can start and end at any nodes. We use a method that remembers best sums from children to avoid repeating work.
Analogy: Imagine a tree of roads with tolls on each road. We want to find the most profitable route that can start and end anywhere, but we calculate profits from bottom roads up to avoid checking every route again and again.
1
/ \
2 3
/ \ \
4 5 6
Each node has a value. We want the max sum path anywhere in this tree.
Goal: Find the maximum sum of values along any path in the tree.
Step 1: Start DFS at node 1, explore left child node 2
Visiting node 1 -> going to node 2
Why: We need to explore children to find max sums from bottom up
Step 2: At node 2, explore left child node 4
Visiting node 2 -> going to node 4
Why: Calculate max path sums from children before using node 2
Step 3: At node 4, no children, max path down = 4, update global max = 4
Node 4 max down = 4, global max = 4
Why: Leaf node max path is its own value
Step 4: Back to node 2, explore right child node 5
Visiting node 2 -> going to node 5
Why: Need max sums from both children to consider paths through node 2
Step 5: At node 5, no children, max path down = 5, update global max = 5
Node 5 max down = 5, global max = 5
Why: Leaf node max path is its own value
Step 6: At node 2, calculate max path down = max(4,5) + 2 = 7; max path through node 2 = 4 + 2 + 5 = 11; update global max = 11
Node 2 max down = 7, global max = 11
Why: Max path can go through node 2 connecting both children
Step 7: Back to node 1, explore right child node 3
Visiting node 1 -> going to node 3
Why: Explore other subtree to find max path
Step 8: At node 3, explore right child node 6
Visiting node 3 -> going to node 6
Why: Calculate max sums from children
Step 9: At node 6, no children, max path down = 6, update global max = 11 (unchanged)
Node 6 max down = 6, global max = 11
Why: Leaf node max path is its own value
Step 10: At node 3, max path down = max(0,6) + 3 = 9; max path through node 3 = 3 + 6 = 9; update global max = 11 (unchanged)
Node 3 max down = 9, global max = 11
Why: Max path through node 3 is less than current global max
Step 11: At node 1, max path down = max(7,9) + 1 = 10; max path through node 1 = 7 + 1 + 9 = 17; update global max = 17
Node 1 max down = 10, global max = 17
Why: Max path through root connects left and right subtrees
Result:
Final max path sum = 17
Path example: 4 -> 2 -> 1 -> 3 -> 6
Annotated Code
DSA Typescript
class TreeNode {
val: number;
children: TreeNode[];
constructor(val: number) {
this.val = val;
this.children = [];
}
}
function maxPathSum(root: TreeNode | null): number {
let maxSum = -Infinity;
function dfs(node: TreeNode | null): number {
if (!node) return0;
// Store max path sums from children
let maxChildSums: number[] = [];
for (const child of node.children) {
const childSum = dfs(child);
maxChildSums.push(childSum);
}
// If no children, max down path is node.val
if (maxChildSums.length === 0) {
maxSum = Math.max(maxSum, node.val);
return node.val;
}
// Sort child sums descending to pick top two
maxChildSums.sort((a, b) => b - a);
// Max path down from this node is node.val + max child sumif positive
const maxDown = node.val + Math.max(0, maxChildSums[0]);
// Max path through this node can include top two child sums if positive
const topTwoSum = node.val +
(maxChildSums[0] > 0 ? maxChildSums[0] : 0) +
(maxChildSums.length > 1 && maxChildSums[1] > 0 ? maxChildSums[1] : 0);
maxSum = Math.max(maxSum, topTwoSum);
return maxDown;
}
dfs(root);
return maxSum;
}
// Driver code to build tree and test
const nodes: {[key: number]: TreeNode} = {};
for (let i = 1; i <= 6; i++) {
nodes[i] = new TreeNode(i);
}
// Build tree edges
nodes[1].children.push(nodes[2], nodes[3]);
nodes[2].children.push(nodes[4], nodes[5]);
nodes[3].children.push(nodes[6]);
console.log(maxPathSum(nodes[1]));
if (!node) return 0;
stop recursion at null nodes
for (const child of node.children) { const childSum = dfs(child); maxChildSums.push(childSum); }
Returns the maximum single node value (least negative)
DSA Typescript
maxSum initialized to -Infinity and updated with Math.max
When to Use This Pattern
When asked to find max sum path in a tree that can start and end anywhere, use DP on trees by computing max path sums from children and combining them at each node.
Common Mistakes
Mistake: Returning sum of all children instead of max path down from one child Fix: Only consider the maximum child path sum for max down path, not sum of all children
Mistake: Not handling negative child sums by including them Fix: Use Math.max(0, childSum) to ignore negative sums
Mistake: Not updating global max with path through node combining two children Fix: Update global max with sum of node value plus top two child sums if positive
Summary
Finds the maximum sum of values along any path in a tree using bottom-up DP.
Use when you need max path sums in trees where paths can start and end anywhere.
Remember to combine max sums from up to two children at each node and track global max.