Given a binary tree, find the maximum path sum. The maximum path sum is defined as the maximum sum of any path from any node to any node in the tree. The path may start and end at any node in the tree.
Table of Contents
Sample Input:
Tree:
1
/ \
2 3
Expected Output:
6
In this example, the maximum path sum is 6, which corresponds to the path: 2 -> 1 -> 3.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to determine the maximum path sum. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
#include <algorithm>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxPathSum(TreeNode* root, int& maxSum) {
// Base case: if the root is null, the maximum path sum is 0
if (root == nullptr) {
return 0;
}
// Recursively calculate the maximum path sum of the left and right subtrees
int leftSum = std::max(0, maxPathSum(root->left, maxSum));
int rightSum = std::max(0, maxPathSum(root->right, maxSum));
// Update the maximum path sum considering the current node as the root of the path
maxSum = std::max(maxSum, root->val + leftSum + rightSum);
// Return the maximum sum that can be extended upward to the parent node
return root->val + std::max(leftSum, rightSum);
}
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN; // Initialize maxSum to the smallest possible integer
maxPathSum(root, maxSum);
return maxSum;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
// Find the maximum path sum of the binary tree
int maxSum = maxPathSum(root);
std::cout << "The maximum path sum of the binary tree is: " << maxSum << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The maxPathSum function recursively calculates the maximum path sum of the binary tree. It starts from the root node and computes the maximum path sum of the left and right subtrees. Then it updates the maximum sum considering the current node as the root of the path. Finally, it returns the maximum sum that can be extended upward to the parent node.
In the given example, the function will correctly find that the maximum path sum of the binary tree is 6, and the output will be 6.
As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.