---
Difficulty: Medium
Source: 160 Days of Problem Solving
Tags:
- Tree
---
# π _Day 8. Maximum path sum from any node_ π§
The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/tree-gfg-160/problem/maximum-path-sum-from-any-node)
## π‘ **Problem Description:**
Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree.
## π **Example Walkthrough:**
**Input:**
`root[] = [10, 2, 10, 20, 1, N, -25, N, N, N, N, 3, 4]`
**Output:**
`42`
**Explanation:**
The maximum path sum is represented using the green colored nodes in the binary tree.
**Input:**
`root[] = [-17, 11, 4, 20, -2, 10]`
**Output:**
`31`
**Explanation:**
The maximum path sum is represented using the green colored nodes in the binary tree.
## Constraints:
- 1 β€ number of nodes β€ $10^3$
- -10^4 β€ node->data β€ $10^4$
## π― **My Approach:**
1. **DFS Post-Order Traversal:**
Use a recursive DFS (post-order) approach to calculate, for each node:
- **maxSingle:** The maximum path sum including the node and at most one of its subtrees.
- **Global Maximum:** Update a global result with the sum of the node value and the maximum contributions from both left and right subtrees.
2. **Steps:**
- Recursively compute the maximum path sum from the left and right children.
- Discard negative sums by taking `max(0, value)`.
- Update the global maximum with `left + right + node->data`.
- Return `node->data + max(left, right)` to allow parent nodes to include the maximum available contribution.
## π **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** O(n), as each node is visited exactly once.
- **Expected Auxiliary Space Complexity:** O(h), where `h` is the height of the tree (due to the recursion stack). In the worst-case (skewed tree), this can be O(n).
## π **Solution Code**
## Code (C++)
```cpp
class Solution {
int dfs(Node* r, int& res) {
if (!r) return 0;
int l = max(0, dfs(r->left, res)), rgt = max(0, dfs(r->right, res));
res = max(res, l + rgt + r->data);
return max(l, rgt) + r->data;
}
public:
int findMaxSum(Node* root) {
int res = INT_MIN;
dfs(root, res);
return res;
}
};
```
π² Alternative Approaches
## **2οΈβ£ Bottom-Up Dynamic Programming Approach**
### **Algorithm**
- Use post-order traversal to compute two values for each node:
- **maxSingle**: Maximum path sum including the current node and at most one child.
- **maxTop**: Maximum path sum where the current node is the highest node (root of the path).
- Recursively compute these values and return the global maximum.
```cpp
class Solution {
pair dfs(Node* r) {
if (!r) return {0, INT_MIN};
auto [lMax, lRes] = dfs(r->left);
auto [rMax, rRes] = dfs(r->right);
int maxSingle = max({r->data, r->data + lMax, r->data + rMax});
int maxTop = max(maxSingle, r->data + lMax + rMax);
return {maxSingle, max({maxTop, lRes, rRes})};
}
public:
int findMaxSum(Node* root) {
return dfs(root).second;
}
};
```
## **3οΈβ£ Iterative Post-Order Traversal Using Stack**
### **Algorithm**
- Perform an **iterative post-order traversal** using a stack.
- Maintain a map to store the maximum path sum for each node.
- For each node, compute:
- **maxSingle**: Max sum including the node and one child.
- **maxTop**: Max sum through the node with both children.
```cpp
class Solution {
public:
int findMaxSum(Node* root) {
if (!root) return 0;
stack s;
unordered_map mp;
Node* last = nullptr;
int res = INT_MIN;
while (root || !s.empty()) {
if (root) s.push(root), root = root->left;
else {
Node* node = s.top();
if (node->right && last != node->right) root = node->right;
else {
s.pop();
int l = max(0, mp[node->left]);
int r = max(0, mp[node->right]);
res = max(res, l + r + node->data);
mp[node] = max(l, r) + node->data;
last = node;
}
}
}
return res;
}
};
```
## π **Comparison of Approaches**
| **Approach** | **Time Complexity** | **Space Complexity** | **Pros** | **Cons** |
| -------------------------------- | ------------------- | --------------------- | --------------------------------- | ----------------------------- |
| **Recursive DFS (Optimized)** | π’ O(N) | π‘ O(H) (stack space) | Clean, concise, easy to implement | Stack overflow for deep trees |
| **Bottom-Up DP** | π’ O(N) | π‘ O(H) | Explicit DP states, easy to debug | Slightly verbose |
| **Iterative Post-Order (Stack)** | π’ O(N) | π‘ O(H) | Avoids recursion stack overflow | More complex logic, verbose |
### π **Best Choice?**
- β
**Balanced Trees:** Recursive DFS is simple and fast.
- β
**Very Deep Trees:** Iterative post-order avoids stack overflow.
- β
**For Debugging/DP:** Bottom-Up DP gives clear intermediate states.
## Code (Java)
```java
class Solution {
int dfs(Node r, int[] res) {
if (r == null) return 0;
int l = Math.max(0, dfs(r.left, res)), rgt = Math.max(0, dfs(r.right, res));
res[0] = Math.max(res[0], l + rgt + r.data);
return Math.max(l, rgt) + r.data;
}
int findMaxSum(Node root) {
int[] res = {Integer.MIN_VALUE};
dfs(root, res);
return res[0];
}
}
```
## Code (Python)
```python
class Solution:
def findMaxSum(self, root):
def dfs(node):
if not node: return 0
l = max(0, dfs(node.left))
r = max(0, dfs(node.right))
nonlocal res
res = max(res, l + r + node.data)
return max(l, r) + node.data
res = float('-inf')
dfs(root)
return res
```
## π― **Contribution and Support:**
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
---
πVisitor Count
