Problem Statement

In a binary tree, a path is a list of nodes where there is an edge between every pair of neighbouring nodes. A node may only make a single appearance in the sequence. The total of each node's values along a path is its path sum. Return the largest path sum of all non-empty paths given the root of a binary tree.

Note: The path does not have to go via the root.

Examples

Example 1:

Input : root = [20, 9, -10, null, null, 15, 7]
Output : 34

Explanation : The path from node 15 to node 9 has maximum path sum.
The path is 15 -> -10 -> 20 -> 9.

Example 2:

Input : root = [-10, 9, 20, null, null, 15, 7]
Output : 42

Explanation : The path from node 15 to node 7 has maximum path sum.
The path is 15 -> 20 -> 7.

Example 3:

Input: root = [1, 2, 3, null, 4]
Output: 10

Different Approaches

1️⃣ Recursive Approach

Intuition:

To determine the maximum path sum in a binary tree, it is essential to consider all possible paths between any two nodes. Since paths can start and end at any node, a comprehensive exploration of every potential path is required, making the problem complex. The primary objective is to identify the path that yields the highest sum. To achieve this, the problem can be decomposed into smaller, more manageable components.

Visualize each node as a potential turning point in the path. For every node, calculate the maximum path sum that includes the node itself and extends through its children. Throughout the traversal, continuously track the highest path sum encountered.

Approach:

1. Begin by defining a recursive function designed to calculate the maximum path sum for each subtree rooted at a given node. If the current node is null, return 0, as there is no valid path through a null node.
2. Proceed by calculating the maximum path sum for both the left and right subtrees. If the path sum for either subtree is negative, it should be disregarded, as including it would decrease the overall sum. This can be achieved by taking the maximum of 0 and the calculated path sum for each subtree.
3. For each node, compute the potential maximum path sum that passes through the node and its children. This sum includes the node itself and the maximum path sums from both subtrees. If this value exceeds the current global maximum sum, update the global maximum to reflect this new higher value.
4. Finally, return the maximum path sum for the current node, considering only one of its subtrees. This step ensures that when the function backtracks up the tree, only the highest path sum from either the left or right subtree is propagated upward, maintaining the integrity of the overall maximum path sum calculation.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    
    // Constructor to initialize the node with a value
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Recursive function to find the maximum path sum
    // for a given subtree rooted at 'root'
    // The variable 'maxi' is a reference parameter
    // updated to store the maximum path sum encountered
    int findMaxPathSum(TreeNode* root, int& maxi) {
        // Base case: If the current node is null, return 0
        if (root == nullptr) {
            return 0;
        }

        // Calculate the maximum path sum
        // for the left and right subtrees
        int leftMaxPath = std::max(0, findMaxPathSum(root->left, maxi));
        int rightMaxPath = std::max(0, findMaxPathSum(root->right, maxi));

        // Update the overall maximum
        // path sum including the current node
        maxi = std::max(maxi, leftMaxPath + rightMaxPath + root->data);

        /*Return the maximum sum considering
        only one branch (either left or right)
        along with the current node */
        return std::max(leftMaxPath, rightMaxPath) + root->data;
    }

    // Function to find the maximum
    // path sum for the entire binary tree
    int maxPathSum(TreeNode* root) {
        // Initialize maxi to the
        // minimum possible integer value
        int maxi = INT_MIN;

        // Call the recursive function to
        // find the maximum path sum
        findMaxPathSum(root, maxi);

        // Return the final maximum path sum
        return maxi;
    }
};

int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->right->right = new TreeNode(6);
    root->left->right->right->right = new TreeNode(7);

    // Creating an instance of the Solution class
    Solution solution;

    // Finding and printing the maximum path sum
    int maxPathSum = solution.maxPathSum(root);
    std::cout << "Maximum Path Sum: " << maxPathSum << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) where N is the number of nodes in the Binary Tree. This complexity arises from visiting each node exactly once during the recursive traversal.
• Space Complexity: O(1) as no additional space or data structures are created that are proportional to the input size of the tree. O(H) Recursive Stack Auxiliary Space