03. Binary Tree Maximum Path Sum

Difficulty:HardPattern:Tree Post-Order DFSTime:O(n)Space:O(h)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. Return the maximum path sum of any non-empty path.

How It Works & Algorithmic Design

Solves using Recursive Post-Order DFS Branch Traversal:

Global Max Variable: Set maxSum = -Infinity.
DFS Function gain(node):
- Base Case: if node === null, return 0.
- Compute max gain from subtrees (ignore negative sums):
  - leftGain = Math.max(0, gain(node.left))
  - rightGain = Math.max(0, gain(node.right))
- Local inverted-V path sum: currentPathSum = node.val + leftGain + rightGain.
- Update global max: maxSum = Math.max(maxSum, currentPathSum).
- Return single branch gain to parent: node.val + Math.max(leftGain, rightGain).

Why This Approach Works Best

Evaluates paths making turning points at any node while passing straight branch sums up to parents in $O(n)$ time and $O(h)$ space.

Example Walkthrough

Input Tree: [-10, 9, 20, null, null, 15, 7]

Binary tree root.

Max Path: 15 -> 20 -> 7 gives max sum = 15 + 20 + 7 = 42

Inverted-V path through node 20.

Output: 42

Maximum path sum.

Answer: Binary Tree Maximum Path Sum implementation

function maxPathSum(root) {
  let maxSum = -Infinity;
  function gain(node) {
    if (!node) return 0;
    const leftGain = Math.max(0, gain(node.left));
    const rightGain = Math.max(0, gain(node.right));
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
    return node.val + Math.max(leftGain, rightGain);
  }
  gain(root);
  return maxSum;
}

💡 Compute maximum gain from left and right subtrees and update running global maximum sum.

Key Takeaways

Use Math.max(0, gain) to prune negative path sum contributions.
Node splits into two branches locally, but returns only one branch to its parent.
Linear time complexity $O(n)$.