Binary Tree Maximum Path Sum hard

Problem Statement

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1

Input: root = [1,2,3] Output: 6 Explanation: The maximum path sum is 2 + 1 + 3 = 6.

Example 2

Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The maximum path sum is 15 + 20 + 7 = 42.

Steps

1. Recursive Approach: We'll use a recursive function to traverse the tree. This function will return the maximum path sum starting from the current node going downwards (either left or right, not both).

2. Maximum Path Sum through Node: For each node, we need to consider three possibilities:

   • The maximum path sum through the current node including only its left subtree.
   • The maximum path sum through the current node including only its right subtree.
   • The maximum path sum through the current node including both its left and right subtrees.

3. Global Maximum: We'll maintain a global variable max_so_far to store the maximum path sum encountered so far across the entire tree.

4. Base Case: If the current node is NULL, return 0.

Explanation

The key idea is that the maximum path sum might not necessarily pass through the root. Therefore, we need to explore all possible paths. Our recursive function calculates the maximum path sum starting from a given node downwards. This is then used to update the global maximum max_so_far. The crucial part is correctly considering the three possibilities mentioned in Step 2. The maximum path sum is updated only if it exceeds the current max_so_far.

Code

#include <iostream>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int max_so_far = INT_MIN; // Initialize with the smallest possible integer

    int maxPathSumHelper(TreeNode* node) {
        if (node == nullptr) return 0;

        int left_max = std::max(0, maxPathSumHelper(node->left)); //Consider only positive values from subtrees
        int right_max = std::max(0, maxPathSumHelper(node->right));

        max_so_far = std::max(max_so_far, node->val + left_max + right_max); //Update global max

        return node->val + std::max(left_max, right_max); //Return max path sum going downwards from current node

    }

    int maxPathSum(TreeNode* root) {
        maxPathSumHelper(root);
        return max_so_far;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In a balanced tree, H would be log N.