Max Path Sum
Find the maximum path sum in a binary tree. The path can start and end at any node.
Max Path Sum Visualizer
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
We need to find a path that maximizes the sum of node values. A path can go up from a left child to the root and then down to the right child. For any node, the max path passing through it (as the highest point) is node.val + max_gain_from_left + max_gain_from_right.
Concept
Tree DP (Post-order Traversal):
We solve this using recursion. For each node, we want two things:
- To Parent: The max path sum starting at this node and going down (to be used by its parent). This is `node.val + max(left_gain, right_gain)`.
- Global Max: The max path sum that pivots at this node. This is `node.val + left_gain + right_gain`. We update a global variable with this value.
Note: If a gain is negative, we ignore it (take 0 instead).
How it Works
Algorithm:
- Initialize `globalMax` to negative infinity.
- Perform a post-order traversal (Left, Right, Root).
- For `node`:
- Recursively get `leftGain = max(0, dfs(node.left))`.
- Recursively get `rightGain = max(0, dfs(node.right))`.
- Update `globalMax = max(globalMax, node.val + leftGain + rightGain)`.
- Return `node.val + max(leftGain, rightGain)` to the parent.
Step-by-Step Breakdown
Visualizing the Tree:
- Bottom-Up: Leaf nodes return their value (if positive).
- Combination: Internal nodes combine gains from children.
- Bridge: The "bridge" formed by `left -> root -> right` is potentially the max path.
When to Use
Applications:
- Network routing (most profitable path).
- Tree analysis (diameter, longest path).
When NOT to Use
- Graphs with Cycles: This algorithm assumes a tree structure (no cycles).
- Fixed Root/Leaf: If path must start at root or end at leaf, the logic simplifies.
How to Identify
"Binary tree", "Maximum path sum", "Any node to any node".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.