Binary Tree Maximum Path Sum
Asked at Amazon, Adobe, Salesforce
Problem
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. The path sum is the sum of the node values. Given the root of a binary tree, return the maximum path sum of any non-empty path.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Adobe | Hard | View all Adobe questions → |
| Salesforce | Hard | View all Salesforce questions → |
How to Think About It
Brute force: for every pair of nodes, find the path between them and compute the sum. This is O(n^2) for a tree. Too slow.
Key insight: at each node, the maximum path either (a) passes through this node (connecting left and right subtrees) or (b) stays within one subtree. Use DFS to compute the maximum "arm" (single-branch path) from each node, and use a global variable to track the maximum path sum overall.
DFS returns the maximum arm sum: the maximum sum of a path starting at this node and going down to one of its children. At each node: compute left_arm = max(0, dfs(left)) and right_arm = max(0, dfs(right)). The path through this node is left_arm + node.val + right_arm. Update the global max. Return node.val + max(left_arm, right_arm) (the arm extending upward).
Why max(0, child_arm): if the child's arm is negative, it is better to not include it (start the path at the current node). This handles trees with all negative values correctly.
Visual walkthrough for tree: -10
/
9 20
/
15 7
DFS on 9: left=0, right=0. path=-10+0+0=-10. max=-10. return -10.
DFS on 15: left=0, right=0. path=15. max=15. return 15.
DFS on 7: left=0, right=0. path=7. max=15. return 7.
DFS on 20: left=max(0,15)=15, right=max(0,7)=7. path=20+15+7=42. max=42. return 20+15=35.
DFS on -10: left=max(0,9)=9, right=max(0,35)=35. path=-10+9+35=34. max=42. return -10+35=25.
Result: 42 (path: 15->20->7).
Time: O(n) — visit each node once. Space: O(h) — recursion stack where h is the tree height.
Optimal Approach
Use DFS with a global variable max_sum.
dfs(node):
- If node is
null, return 0. left = max(0, dfs(node.left))— max arm from left (clamp negatives to 0).right = max(0, dfs(node.right))— max arm from right.path_through_node = left + node.val + right. Updatemax_sum = max(max_sum, path_through_node).- Return
node.val + max(left, right)— the arm extending to parent.
Walkthrough: tree with root=-10, left=9, right=20 (left=15, right=7).
dfs(9): left=0, right=0. path=9. max=9. return 9.dfs(15): path=15. max=15. return 15.dfs(7): path=7. max=15. return 7.dfs(20): left=15, right=7. path=20+15+7=42. max=42. return 20+15=35.dfs(-10): left=max(0,9)=9, right=max(0,35)=35. path=-10+9+35=34. max=42.
Result: 42.
Time: O(n). Space: O(h).
What Trips People Up in Real Interviews
Forgetting to clamp child arm values to 0 with max(0, child_arm). If a subtree has a negative sum, including it would decrease the path sum. Clamping to 0 means "don't include this subtree." Without this, the algorithm fails on trees with negative values.
Confusing "path" with "path from root to leaf." A path can start and end at any node. The path through a node connects its left and right subtrees. This is different from root-to-leaf paths.
Returning left + node.val + right from DFS instead of node.val + max(left, right). The DFS must return the maximum arm (single branch) for the parent to use. Returning the full path through the node would double-count when the parent uses it.
Not using a global or class-level variable for max_sum. The recursive DFS cannot easily return both the arm sum and the global max. Use a class variable, a nonlocal variable (Python), or pass a mutable reference.
Handling single-node trees. If the tree has one node with a negative value, the answer is that negative value (the path is just that node). The algorithm handles this correctly because max_sum is initialized to negative infinity and the path through the single node is its value.
Solution Code
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root):
self.max_sum = float('-inf')
def dfs(node):
if not node:
return 0
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
self.max_sum = max(self.max_sum, left + node.val + right)
return node.val + max(left, right)
dfs(root)
return self.max_sumFrequently Asked Questions
What is the Binary Tree Maximum Path Sum problem?
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. The path sum is the sum of the node values. Given the root of a binary tree, return the maximum path sum of any non-empty path.
How do you solve Binary Tree Maximum Path Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Maximum Path Sum?
Binary Tree Maximum Path Sum is asked at Amazon, Adobe, Salesforce. It is a hard difficulty problem.
What are common mistakes on Binary Tree Maximum Path Sum?
- Forgetting to clamp child arm values to 0 with `max(0, child_arm)`. If a subtree has a negative sum, including it would decrease the path sum. Clamping to 0 means "don't include this subtree." Without this, the algorithm fails on trees with negative values.
- Confusing "path" with "path from root to leaf." A path can start and end at any node. The path through a node connects its left and right subtrees. This is different from root-to-leaf paths.
- Returning `left + node.val + right` from DFS instead of `node.val + max(left, right)`. The DFS must return the maximum arm (single branch) for the parent to use. Returning the full path through the node would double-count when the parent uses it.
- Not using a global or class-level variable for `max_sum`. The recursive DFS cannot easily return both the arm sum and the global max. Use a class variable, a nonlocal variable (Python), or pass a mutable reference.
- Handling single-node trees. If the tree has one node with a negative value, the answer is that negative value (the path is just that node). The algorithm handles this correctly because `max_sum` is initialized to negative infinity and the path through the single node is its value.