Find the highest sum you can get by traveling along any path in the tree, where a path can start and end at any node.
Analogy: Imagine a mountain range where each peak has a height (value). You want to find the highest possible trail that can go up and down connecting peaks, but you cannot jump around; you must walk along connected peaks.
Goal: Find the maximum path sum anywhere in the tree, which can start and end at any node.
Step 1: Start at leaf node 20, max path sum from here is 20
20 (leaf) -> max path sum = 20
Why: Leaf nodes have max path sum equal to their own value
Step 2: At node 1 (leaf), max path sum is 1
1 (leaf) -> max path sum = 1
Why: Leaf nodes have max path sum equal to their own value
Step 3: At node 2, calculate max path sum including left and right children: max(20,0)+2+max(1,0)=23; max path sum from node 2 to parent is 2 + max(20,1) = 22
2 -> left=20, right=1 -> max path sum through node 2 = 23, max path sum to parent = 22
Why: We consider max path through node 2 and also max path to parent for further calculation
Step 4: At node 3 (leaf), max path sum is 3
3 (leaf) -> max path sum = 3
Why: Leaf nodes have max path sum equal to their own value
Step 5: At node 4 (leaf), max path sum is 4
4 (leaf) -> max path sum = 4
Why: Leaf nodes have max path sum equal to their own value
Step 6: At node -25, calculate max path sum including children: max(3,0)+(-25)+max(4,0) = -18; max path sum to parent is -25 + max(3,4) = -21
-25 -> left=3, right=4 -> max path sum through node -25 = -18, max path sum to parent = -21
Why: Negative node reduces sum, but we still consider max path to parent
Step 7: At node 10 (right child of root), max path sum to parent is 10 + max(0, -21) = 10; max path sum through node is 10
10 (right child) -> max path sum to parent = 10, max path sum through node = 10
Why: Right child has no left child, and right child's right subtree max path sum to parent is negative, so ignored
Step 8: At root 10, calculate max path sum including left and right children: max(22,0)+10+max(10,0) = 42; max path sum to parent is 10 + max(22,10) = 32
root 10 -> left=22, right=10 -> max path sum through root = 42, max path sum to parent = 32
Why: Root combines best paths from left and right to find max path sum in entire tree
Result:
Maximum path sum in tree = 42
Final max path: 20 -> 2 -> 10 -> 10
Annotated Code
DSA Typescript
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
function maxPathSum(root: TreeNode | null): number {
let maxSum = -Infinity;
function helper(node: TreeNode | null): number {
if (node === null) return0;
// Recursively get max path sumfrom left and right children
const leftMax = Math.max(helper(node.left), 0); // ignore negative sums
const rightMax = Math.max(helper(node.right), 0); // ignore negative sums
// Calculate max path sum passing through current node
const currentSum = node.val + leftMax + rightMax;
// Update global maxSum if currentSum is higher
maxSum = Math.max(maxSum, currentSum);
// Return max path sum including current node and one subtree to parent
return node.val + Math.max(leftMax, rightMax);
}
helper(root);
return maxSum;
}
// Driver code to build tree and test
const root = new TreeNode(10,
new TreeNode(2,
new TreeNode(20),
new TreeNode(1)
),
new TreeNode(10,
null,
new TreeNode(-25,
new TreeNode(3),
new TreeNode(4)
)
)
);
console.log(maxPathSum(root));
if (node === null) return 0;
stop recursion at leaf's child
const leftMax = Math.max(helper(node.left), 0);
get max path sum from left child, ignore negative sums
const rightMax = Math.max(helper(node.right), 0);
get max path sum from right child, ignore negative sums
const currentSum = node.val + leftMax + rightMax;
calculate max path sum passing through current node
maxSum = Math.max(maxSum, currentSum);
update global max if current path sum is higher
return node.val + Math.max(leftMax, rightMax);
return max path sum including current node and one subtree to parent
OutputSuccess
42
Complexity Analysis
Time: O(n) because we visit each node once in the tree
Space: O(h) where h is tree height due to recursion stack
vs Alternative: Naive approach might try all paths explicitly causing exponential time; this approach uses recursion and pruning negative sums for linear time
Edge Cases
Empty tree (root is null)
Returns -Infinity or 0 depending on implementation; here returns -Infinity as no nodes exist
DSA Typescript
if (node === null) return0;
Tree with all negative values
Ignores negative child sums but still considers node's own value; returns the least negative node value
DSA Typescript
const leftMax = Math.max(helper(node.left), 0);
Single node tree
Returns the value of the single node as max path sum
DSA Typescript
if (node === null) return0;
When to Use This Pattern
When asked to find the maximum sum path in a tree that can start and end anywhere, use the max path sum pattern with recursion and tracking global max.
Common Mistakes
Mistake: Returning sum of both children to parent causing invalid paths Fix: Return node value plus max of one child's max path sum only
Mistake: Not ignoring negative sums from children, which lowers max path sum Fix: Use Math.max(childSum, 0) to ignore negative sums
Summary
Finds the highest sum path in a binary tree that can start and end at any node.
Use when you need the maximum sum of connected nodes in any path within a tree.
The key is to track max sums from children ignoring negatives and update a global max including both children.