Binary Tree Maximum Path Sum Hard 0 attempts
LeetCode ↗

Binary Tree Maximum Path Sum

Hard TreeBinary TreeDFS LeetCode

Given a binary tree, find the maximum path sum. A path is any sequence of nodes connected by edges where each node appears at most once. The path does not need to pass through the root.

Example: root = [-10,9,20,null,null,15,7] → Output: 42 (15→20→7)

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 3 * 10^4
  • -1000 <= Node.val <= 1000
Topics
TreeBinary TreeDFS

DFS with Global Max

For each node, compute the max single-path sum through it and update global max.

function maxPathSum(root) {
  let max = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    const l = Math.max(0, dfs(node.left));
    const r = Math.max(0, dfs(node.right));
    max = Math.max(max, l + r + node.val);
    return Math.max(l, r) + node.val;
  }
  dfs(root);
  return max;
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.

JavaScript