Overview

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has a parent-child edge. The path does not need to pass through the root, and each node can appear at most once in the path.

Given the root of a binary tree, return the maximum path sum — the largest sum of node values along any path in the tree.

Constraints

• The tree has 1 to 10,000 nodes.
• Node values can be negative (range: -1000 to 1000).
• A path must contain at least one node.
• The path can start and end at any node.

Examples

// Tree:
//       1
//      / \
//     2   3
maxPathSum({ val: 1, left: { val: 2, left: null, right: null }, right: { val: 3, left: null, right: null } });
// => 6  (path: 2 -> 1 -> 3)

// Tree with negatives:
//      -10
//      / \
//     9   20
//        / \
//      15   7
maxPathSum({
  val: -10,
  left: { val: 9, left: null, right: null },
  right: { val: 20, left: { val: 15, left: null, right: null }, right: { val: 7, left: null, right: null } }
});
// => 42  (path: 15 -> 20 -> 7)

Solution

function maxPathSum(root) {
  let maxSum = -Infinity;

  function dfs(node) {
    if (node === null) return 0;
    const leftGain = Math.max(dfs(node.left), 0);
    const rightGain = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
    return node.val + Math.max(leftGain, rightGain);
  }

  dfs(root);
  return maxSum;
}

Resources

• Binary Tree Maximum Path Sum — LeetCode
• DFS on Trees — GeeksforGeeks