Skip to main content

Binary Tree Maximum Path Sum

Problem​

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    int ans;
    map<TreeNode*, int> mp;

   public:
    void traversal(TreeNode* root) {
        if (!root) return;
        traversal(root->left);
        traversal(root->right);

        ans = max(ans, root->val);

        int value = root->val;
        if (root->right) value += mp[root->right];
        if (root->left) value += mp[root->left];

        ans = max(ans, value);
        mp[root] = max({root->val, root->val + mp[root->right],
                        root->val + mp[root->left]});
        ans = max(ans, mp[root]);
    }

    int maxPathSum(TreeNode* root) {
        ans = INT_MIN;
        traversal(root);
        return ans;
    }
};