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.
Example 1:
Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
[1, 3 * 104].-1000 <= Node.val <= 1000The key challenge in Binary Tree Maximum Path Sum is that a valid path can start and end at any node, but it must follow parent–child connections. A common strategy is to use Depth-First Search (DFS) combined with ideas from dynamic programming. During traversal, compute the maximum gain a node can contribute to its parent.
For each node, recursively calculate the best contribution from its left and right children. If a child contributes a negative sum, it is better to ignore it by treating its contribution as 0. The current node can then form a candidate path using left_gain + node.val + right_gain, which may update a global maximum path sum.
The value returned to the parent should represent the best single-branch extension, meaning the node value plus the larger of the two child gains. This ensures paths remain continuous. The tree is processed once, giving a time complexity of O(n), while recursion depth leads to O(h) space usage where h is the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Dynamic Programming (Max Gain per Node) | O(n) | O(h) |
take U forward
This approach uses a recursive depth-first search (DFS) to explore every path in the binary tree. We calculate the maximum path sum that a node can contribute to its parent, which is the largest possible sum of the path from this node to any leaf node passing through this node. We keep updating the global maximum path sum during the recursion.
Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.
Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack for recursion.
1#include <limits.h>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12 int maxPathSum(TreeNode* root) {
13 int max_sum = INT_MIN;
14 maxGain(root, max_sum);
15 return max_sum;
16 }
17
18 int maxGain(TreeNode* node, int &max_sum) {
19 if (!node) return 0;
20 int left_gain = std::max(maxGain(node->left, max_sum), 0);
21 int right_gain = std::max(maxGain(node->right, max_sum), 0);
22 int price_newpath = node->val + left_gain + right_gain;
23 max_sum = std::max(max_sum, price_newpath);
24 return node->val + std::max(left_gain, right_gain);
25 }
26};The solution uses a similar recursive method named maxGain as in the Python approach. This method computes the maximum gain from children nodes while traversing the tree. For each node, it calculates left_gain and right_gain and updates the max_sum if the sum rooted at the current node is greater. This helps in maintaining the maximum path sum. As compared to the Python approach, error checks like returning early from null nodes are done explicitly.
In this approach, we utilize dynamic programming principles alongside tree traversal to compute the maximum path sum. This method is more about reformulating the tree's recursive structure into a form that allows storing intermediate results to optimize operations across the different subtrees. This method is especially useful for understanding different formulations but often overlaps logically with recursive DFS.
Time Complexity: O(n), covering a single pass over all nodes.
Space Complexity: O(h), necessitated by call stack usage designated by the tree height h.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int maxSum = int.MinValue;
public int MaxPathSum(TreeNode root) {
CalculateMaxSum(root);
return maxSum;
}
private int CalculateMaxSum(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.Max(CalculateMaxSum(node.left), 0);
int rightGain = Math.Max(CalculateMaxSum(node.right), 0);
int currentPath = node.val + leftGain + rightGain;
maxSum = Math.Max(maxSum, currentPath);
return node.val + Math.Max(leftGain, rightGain);
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this is a well-known hard-level tree problem frequently discussed in FAANG-style interviews. It tests understanding of tree traversal, recursion, and dynamic programming concepts applied to hierarchical structures.
The problem primarily uses a binary tree along with recursion (DFS). A global variable or reference is typically maintained to track the maximum path sum encountered during traversal.
The optimal approach uses Depth-First Search with a dynamic programming idea of computing the maximum gain from each node. While traversing, you track the best path passing through each node and update a global maximum. This ensures every node is processed once.
Negative subtree sums reduce the total path value. By treating negative contributions as zero, the algorithm ensures that only beneficial branches are included in the candidate path sum. This helps maximize the overall result.
The C# implementation follows a similar recursive pattern to manage sub-problem solutions through CalculateMaxSum. It ensures that each recurred call provides cumulative knowledge to effectively contribute towards deriving a maximum path sum that encompasses any tree node as a potential root towards assessing the best path sum.