Problem Statement:
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.
Examples:
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:
- The number of nodes in the tree is in the range
[1, 3 * 104]. -1000 <= Node.val <= 1000
Approach
- At each node, calculate:
maxLeft: max gain from the left subtree (0 if negative)maxRight: max gain from the right subtree (0 if negative)
- The local max path passing through current node is:
curr.val + maxLeft + maxRight - Update the global max sum (
maxSumPath) with the local max. - Return the max gain to the parent node:
curr.val + max(maxLeft, maxRight)
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h)(h=tree height)
Dry Run
Function Call: maxPathSum(root) where
root = Node(1)
├── left: Node(2)
│ ├── left: Node(4)
│ └── right: Node(5)
└── right: Node(3)
├── left: Node(6)
└── right: Node(7)
Step 1:
→ Call traversal(curr = 1)
→ Call traversal(curr = 2)
→ Call traversal(curr = 4)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 4 + 0 + 0 = 4
→ maxSumPath = max(-Infinity, 4) = 4
→ return 4
→ Call traversal(curr = 5)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 5 + 0 + 0 = 5
→ maxSumPath = max(4, 5) = 5
→ return 5
→ Now at curr = 2
→ maxLeft = 4, maxRight = 5
→ currMax = 2 + 4 + 5 = 11
→ maxSumPath = max(5, 11) = 11
→ return 2 + max(4, 5) = 7
→ Call traversal(curr = 3)
→ Call traversal(curr = 6)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 6 + 0 + 0 = 6
→ maxSumPath = max(11, 6) = 11
→ return 6
→ Call traversal(curr = 7)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 7 + 0 + 0 = 7
→ maxSumPath = max(11, 7) = 11
→ return 7
→ Now at curr = 3
→ maxLeft = 6, maxRight = 7
→ currMax = 3 + 6 + 7 = 16
→ maxSumPath = max(11, 16) = 16
→ return 3 + max(6, 7) = 10
→ Back at root = 1
→ maxLeft = 7, maxRight = 10
→ currMax = 1 + 7 + 10 = 18
→ maxSumPath = max(16, 18) = 18
→ return 1 + max(7, 10) = 11
Final Result: 18 is the maximum path sum in the binary tree.
root = Node(1)
├── left: Node(2)
│ ├── left: Node(4)
│ └── right: Node(5)
└── right: Node(3)
├── left: Node(6)
└── right: Node(7)
Step 1:
→ Call traversal(curr = 1)
→ Call traversal(curr = 2)
→ Call traversal(curr = 4)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 4 + 0 + 0 = 4
→ maxSumPath = max(-Infinity, 4) = 4
→ return 4
→ Call traversal(curr = 5)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 5 + 0 + 0 = 5
→ maxSumPath = max(4, 5) = 5
→ return 5
→ Now at curr = 2
→ maxLeft = 4, maxRight = 5
→ currMax = 2 + 4 + 5 = 11
→ maxSumPath = max(5, 11) = 11
→ return 2 + max(4, 5) = 7
→ Call traversal(curr = 3)
→ Call traversal(curr = 6)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 6 + 0 + 0 = 6
→ maxSumPath = max(11, 6) = 11
→ return 6
→ Call traversal(curr = 7)
→ traversal(curr.left) = 0 (null)
→ traversal(curr.right) = 0 (null)
→ currMax = 7 + 0 + 0 = 7
→ maxSumPath = max(11, 7) = 11
→ return 7
→ Now at curr = 3
→ maxLeft = 6, maxRight = 7
→ currMax = 3 + 6 + 7 = 16
→ maxSumPath = max(11, 16) = 16
→ return 3 + max(6, 7) = 10
→ Back at root = 1
→ maxLeft = 7, maxRight = 10
→ currMax = 1 + 7 + 10 = 18
→ maxSumPath = max(16, 18) = 18
→ return 1 + max(7, 10) = 11
Final Result: 18 is the maximum path sum in the binary tree.
var maxPathSum = function(root) {
let maxSumPath = -Infinity;
let traversal = (curr) => {
if(!curr) return 0;
let maxLeft = Math.max(0, traversal(curr.left));
let maxRight = Math.max(0, traversal(curr.right));
currMax = curr.val + maxLeft + maxRight;
maxSumPath = Math.max(currMax, maxSumPath);
return curr.val + Math.max(maxLeft, maxRight);
}
traversal(root);
return maxSumPath;
};
class Solution:
def maxPathSum(self, root):
self.maxSumPath = float('-inf')
def traversal(node):
if not node:
return 0
maxLeft = max(0, traversal(node.left))
maxRight = max(0, traversal(node.right))
currMax = node.val + maxLeft + maxRight
self.maxSumPath = max(self.maxSumPath, currMax)
return node.val + max(maxLeft, maxRight)
traversal(root)
return self.maxSumPath
class Solution {
private int maxSumPath = Integer.MIN_VALUE;
private int traversal(TreeNode root) {
if (root == null) return 0;
int maxLeft = Math.max(0, traversal(root.left));
int maxRight = Math.max(0, traversal(root.right));
int currMax = root.val + maxLeft + maxRight;
maxSumPath = Math.max(maxSumPath, currMax);
return root.val + Math.max(maxLeft, maxRight);
}
public int maxPathSum(TreeNode root) {
traversal(root);
return maxSumPath;
}
}
class Solution {
public:
int maxSumPath = INT_MIN;
int traversal(TreeNode* root) {
if (!root) return 0;
int maxLeft = max(0, traversal(root->left));
int maxRight = max(0, traversal(root->right));
int currMax = root->val + maxLeft + maxRight;
maxSumPath = max(maxSumPath, currMax);
return root->val + max(maxLeft, maxRight);
}
int maxPathSum(TreeNode* root) {
traversal(root);
return maxSumPath;
}
};
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int maxSumPath;
int max(int a, int b) {
return (a > b) ? a : b;
}
int traversal(struct TreeNode* root) {
if (!root) return 0;
int maxLeft = max(0, traversal(root->left));
int maxRight = max(0, traversal(root->right));
int currMax = root->val + maxLeft + maxRight;
if (currMax > maxSumPath) maxSumPath = currMax;
return root->val + max(maxLeft, maxRight);
}
int maxPathSum(struct TreeNode* root) {
maxSumPath = INT_MIN;
traversal(root);
return maxSumPath;
}
public class Solution {
private int maxSumPath = int.MinValue;
private int Traversal(TreeNode root) {
if (root == null) return 0;
int maxLeft = Math.Max(0, Traversal(root.left));
int maxRight = Math.Max(0, Traversal(root.right));
int currMax = root.val + maxLeft + maxRight;
maxSumPath = Math.Max(maxSumPath, currMax);
return root.val + Math.Max(maxLeft, maxRight);
}
public int MaxPathSum(TreeNode root) {
Traversal(root);
return maxSumPath;
}
}
