Leetcode 124. Binary Tree Maximum Path Sum
Find the maximum sum of any non-empty connected path in a binary tree (nodes used at most once), where the path can start and end at any nodes and node values may be negative. You must account for single-node paths when all values are negative.
Asked at:
Doordash
Datadog
Amazon
Salesforce
DESCRIPTION
Find the maximum sum of any non-empty connected path in a binary tree (nodes used at most once), where the path can start and end at any nodes and node values may be negative. You must account for single-node paths when all values are negative.
Input:
nodes = [1, 2, 3]
Output:
6
Explanation: The optimal path is 2 -> 1 -> 3, which connects both subtrees through the root. Sum is 2 + 1 + 3 = 6
Constraints:
- The number of nodes in the tree is in the range [1, 3 * 10^4]
- -1000 <= Node.val <= 1000
- Node values can be negative
- A path must contain at least one node
Understanding the Problem
Let's understand what we're being asked to do. We have a binary tree where each node contains a value (which can be negative), and we need to find the maximum sum of any path.
A path is a sequence of connected nodes where each node appears at most once. The path can start and end at any nodes - it doesn't have to go through the root!
For example, in a tree with values [1, 2, 3] where 1 is root with children 2 and 3, the path 2 -> 1 -> 3 has sum 2+1+3 = 6. But we could also consider just the single node path 3 with sum 3, or the path 1 -> 3 with sum 4.
Critical constraint: When all values are negative (like [-3, -2, -1]), we must still return a valid path. The best choice would be the single-node path with the least negative value (in this case, -1).
Edge cases to consider: What if the tree has only one node? What if we have a path that goes down one subtree, through a node, and down another subtree? What if including a parent node actually decreases our sum?
Building Intuition
At each node, we face a decision: should we extend a path from one of our subtrees through ourselves, or should we connect paths from both subtrees through ourselves?
For example, if our left subtree offers a path sum of 10, our right subtree offers 15, and our value is 5, we could:
- Extend left: 10 + 5 = 15
- Extend right: 15 + 5 = 20
- Connect both: 10 + 5 + 15 = 30
The key insight is that a connecting path (using both subtrees) cannot be extended further upward, but an extending path (using one subtree) can be part of a larger path.
This means at each node, we need to track TWO different values:
- The maximum path sum that passes through this node (potentially connecting both subtrees)
- The maximum path sum we can contribute upward to our parent (can only use one subtree)
The global answer is the maximum of all "passing through" sums, but what we return to our parent is the "contribute upward" value.
Think of each node as a bridge between two islands (left and right subtrees). You can:
- Walk across the bridge and continue to one island (extending path)
- Walk from one island, across the bridge, to the other island (connecting path - but now you're stuck, can't go further)
As you explore the tree, you're constantly asking: "What's the best path I can make here?" and "What's the best contribution I can offer to my parent?"
When values are negative, you might choose to not include a subtree at all (contributing 0 is better than adding a negative sum).
Common Mistakes
Optimal Solution
Use a recursive depth-first search (DFS) to explore the tree. At each node, calculate the maximum path sum that can be contributed upward (using at most one subtree) and the maximum path sum passing through this node (potentially using both subtrees). Track the global maximum across all nodes. For each subtree, we take the maximum of its contribution or zero (to handle negative sums). Return the best single-path contribution upward while updating the global maximum with the best connecting path at each node.
def max_path_sum(root):"""Find maximum path sum in binary tree using DFS.Path can start and end at any nodes."""# Track global maximum across all pathsmax_sum = [float('-inf')]def dfs(node):# Base case: empty node contributes 0if not node:return 0# Recursively get max contribution from left subtreeleft_contribution = dfs(node.left)# Recursively get max contribution from right subtreeright_contribution = dfs(node.right)# Take max of subtree contribution or 0 (ignore negative paths)left_max = max(left_contribution, 0)right_max = max(right_contribution, 0)# Calculate path sum passing through current node (using both subtrees)path_through_node = node.val + left_max + right_max# Update global maximum with path through this nodemax_sum[0] = max(max_sum[0], path_through_node)# Return best single-path contribution upward (can only use one subtree)return node.val + max(left_max, right_max)# Start DFS from rootdfs(root)# Return the global maximum path sum foundreturn max_sum[0]
Start finding maximum path sum in binary tree
0 / 44
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We visit each node exactly once in the tree, where n is the number of nodes. At each node, we perform constant-time operations (comparing sums, taking maximums).
Space Complexity: O(h) The space complexity is determined by the recursion call stack, which in the worst case (skewed tree) is O(n), but for a balanced tree is O(log n). We use h to represent the height of the tree.
What We've Learned
- Post-order DFS for path aggregation: When you need to compute values that depend on subtree results (like maximum path sums), use post-order traversal - process children first, then combine their results at the parent. This bottom-up approach ensures you have all necessary information before making decisions at each node.
- Dual-value return pattern: Distinguish between the value you return to parent (single-path sum for extension) versus the global answer you track (complete path sum). Return only the maximum single-branch path (node + max of left or right), but update global max with the full path (node + left + right) - this prevents invalid path shapes.
- Negative value handling with max(0, subtree): When dealing with potentially negative node values, use max(0, childSum) to decide whether to include a subtree. This elegantly handles the case where extending the path would decrease the sum - simply don't extend it. Never skip processing a node itself though, as it might be the best single-node path.
- Global variable for cross-subtree optimization: Use a global/nonlocal variable to track the maximum across all recursive calls, because the optimal path might not pass through the root and could span disconnected subtrees. The return value alone can't capture paths that branch in both directions at intermediate nodes.
- Path shape constraint awareness: Recognize that a valid path is linear or V-shaped (up to one turn), never Y-shaped. At each node, you can combine left subtree + node + right subtree for the global answer, but can only return node + one subtree upward, preventing the parent from creating an invalid multi-branched path.
- Single-node base case importance: Always consider that the optimal path might be a single node, especially with negative values. Initialize your global max to the first node's value or negative infinity, not zero, because an all-negative tree still needs to return its least negative node.
Related Concepts and Problems to Practice
This lesson directly teaches the pattern needed for Binary Tree Maximum Path Sum - using helper functions with global variables to track optimal values while recursing through a tree. This is the exact technique required to solve the maximum path sum problem where you need to track the global maximum while computing local path values.
easy
This problem uses the identical pattern to Maximum Path Sum - computing a global maximum (diameter) while recursively returning local values (height). Both require tracking two different metrics: what you return up the tree versus what you track globally, making it perfect practice for understanding the path sum problem.
medium
This problem extends the same pattern to paths with constraints, where you compute the longest path through each node while returning different values up the recursion. Like Maximum Path Sum, it requires distinguishing between paths that continue upward versus complete paths through a node, making it excellent practice for mastering this tree DFS pattern.
Test Your Understanding
Why is tree the right data structure for this problem?
tree provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid December, 2025
Meta
Senior
Mid November, 2025
Salesforce
Mid-level
Late July, 2025
Doordash
Mid-level
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.