Binary Tree Maximum Path Sum Visualizer & Step-by-Step Algorithm Solution

Find the maximum path sum along any sequence of nodes in a binary tree using bottom-up postorder DFS (ignoring negative subtrees).

Category: trees | Difficulty: Hard

Tags: DFS, Binary Tree, Recursion, Path Sum, Hard, Postorder

Binary Tree Maximum Path Sum

-10
9
20
15
7
100%
state
maxPathSum-∞
maxSum-∞
Initialization
1/38
Explanation

Start maxPathSum on binary tree with root: Node(-10). Initial maxSum = -∞.

Source Code
1function maxPathSum(root) {
2 let maxSum = -Infinity;
3 function dfs(node) {
4 if (!node) return 0;
5 const leftGain = Math.max(0, dfs(node.left));
6 const rightGain = Math.max(0, dfs(node.right));
7 const currentPath = node.val + leftGain + rightGain;
8 maxSum = Math.max(maxSum, currentPath);
9 return node.val + Math.max(leftGain, rightGain);
10 }
11 dfs(root);
12 return maxSum;
13}