Approach Summary
Post-order DFS returns max gain from each node. At each node, consider the path through it (left + node + right) to update global max.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Post-Order DFS with Maximum Branch Gain (Optimal) | O(n) | O(h) | Compute max branch gain per node, updating global max with left + right + node.val. |
| 2 Approach 2: Two-Phase DFS from Every Candidate Root (Baseline) | O(n²) | O(h) | Recursively calculates max downward path from each child and computes root-spanning path for every node. |
Step 1: Baseline
Approach 1: Post-Order DFS with Maximum Branch Gain (Optimal)
Time: O(n)
Space: O(h)
For each node, compute the maximum gain obtainable from its left and right subtrees (clamped at 0 to avoid negative drag). The turning path at this node is left + right + node.val, which updates the global maximum. To the parent, return node.val + max(left, right).
Approach 1: Post-Order DFS with Maximum Branch Gain (Optimal) Implementation
Approach 1: Post-Order DFS with Maximum Branch Gain (Optimal)
class Solution {
private int maxSum = Integer.MIN_VALUE;
private int gain(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, gain(node.left));
int right = Math.max(0, gain(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return node.val + Math.max(left, right);
}
public int maxPathSum(TreeNode root) {
gain(root);
return maxSum;
}
}class Solution {
public:
int maxSum = INT_MIN;
int gain(TreeNode* root) {
if (!root) return 0;
int left = max(0, gain(root->left));
int right = max(0, gain(root->right));
maxSum = max(maxSum, left + right + root->val);
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
gain(root);
return maxSum;
}
};class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.max_sum = float('-inf')
def dfs(node):
if not node:
return 0
l = max(0, dfs(node.left))
r = max(0, dfs(node.right))
self.max_sum = max(self.max_sum, l + r + node.val)
return node.val + max(l, r)
dfs(root)
return self.max_sumfunction maxPathSum(root) {
let maxSum = -Infinity;
function solve(node) {
if (!node) return 0;
const left = Math.max(0, solve(node.left));
const right = Math.max(0, solve(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return node.val + Math.max(left, right);
}
solve(root);
return maxSum;
} Step 2: Most Optimized
Approach 2: Two-Phase DFS from Every Candidate Root (Baseline)
Time: O(n²)
Space: O(h)
For each node in the tree, we run a helper function to find the maximum downward single-branch path from left and right children. The path through node is node.val + max(0, left) + max(0, right). We maximize this over all nodes in the tree.
Approach 2: Two-Phase DFS from Every Candidate Root (Baseline) Implementation
Approach 2: Two-Phase DFS from Every Candidate Root (Baseline)
class Solution {
private int ans = Integer.MIN_VALUE;
private int maxDown(TreeNode node) {
if (node == null) return 0;
return Math.max(0, node.val + Math.max(maxDown(node.left), maxDown(node.right)));
}
private void dfs(TreeNode node) {
if (node == null) return;
ans = Math.max(ans, node.val + maxDown(node.left) + maxDown(node.right));
dfs(node.left);
dfs(node.right);
}
public int maxPathSum(TreeNode root) {
dfs(root);
return ans;
}
}class Solution {
int ans = INT_MIN;
int maxDown(TreeNode* node) {
if (!node) return 0;
return max(0, node->val + max(maxDown(node->left), maxDown(node->right)));
}
void dfs(TreeNode* node) {
if (!node) return;
ans = max(ans, node->val + maxDown(node->left) + maxDown(node->right));
dfs(node->left);
dfs(node->right);
}
public:
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def max_down(node):
if not node: return 0
return max(0, node.val + max(max_down(node.left), max_down(node.right)))
self.ans = float('-inf')
def dfs(node):
if not node: return
self.ans = max(self.ans, node.val + max_down(node.left) + max_down(node.right))
dfs(node.left)
dfs(node.right)
dfs(root)
return self.ansfunction maxPathSum(root) {
let ans = -Infinity;
function maxDown(node) {
if (!node) return 0;
return Math.max(0, node.val + Math.max(maxDown(node.left), maxDown(node.right)));
}
function dfs(node) {
if (!node) return;
ans = Math.max(ans, node.val + maxDown(node.left) + maxDown(node.right));
dfs(node.left);
dfs(node.right);
}
dfs(root);
return ans;
}Edge Cases to Watch
- All node values are negative (e.g. [-3]; returns -3, the single largest negative value)
- Path does not pass through root (e.g. best path is in a deep subtree)
- Single node tree
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Max path sum through any node
- Post-order with global variable
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree DFS DP
Frequently Asked Questions
What is the optimal time and space complexity for Binary Tree Maximum Path Sum?
The optimal solution for Binary Tree Maximum Path Sum achieves O(n) runtime complexity and requires O(h) auxiliary space. Time complexity is O(n) because each node is visited once in post-order DFS. Space complexity is O(h) for the recursion stack.
How do I identify that Binary Tree Maximum Path Sum requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Max path sum through any node; Post-order with global variable. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Binary Tree Maximum Path Sum?
Essential edge cases to verify include: All node values are negative (e.g. [-3]; returns -3, the single largest negative value); Path does not pass through root (e.g. best path is in a deep subtree); Single node tree. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Binary Tree Maximum Path Sum?
Binary Tree Maximum Path Sum is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Apple.