loading

Binary Tree Maximum Path Sum — Step-by-Step Visualization

hardLeetCode #124TreeDepth-First SearchDynamic ProgrammingBinary Tree

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Algorithm Pattern

Recursive Path Accumulation

Key Idea

For any node, the maximum path sum that 'passes through' it is its own value plus the maximum contribution from its left child (if positive) and its right child (if positive). We use a recursive DFS to: (1) update a global maximum across all nodes, and (2) return the single-branch maximum to its parent.

Step-by-Step Approach

  1. Initialize `maxPathSum = -Infinity`.
  2. Recursive DFS: At each node, calculate the max gain from its left and right children. Ignore negative gains (treat as 0).
  3. Update Global: `maxPathSum = max(maxPathSum, node.val + left_gain + right_gain)`.
  4. Return to Parent: `node.val + max(left_gain, right_gain)`.

Common Gotchas

  • Negative values are the biggest hurdle. If a subtree's maximum gain is negative, we're better off not including that subtree in our path at all.
  • The path can be just a single node if all its neighbors and their descendants are very negative.

Related Problems

← All problems