Maximum path sum

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

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.
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.
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.
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

Solution

#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;
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null, right = null; }
 * }
 **/

class Solution {
    /* 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 == null) {
            return 0;
        }

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

        // Update the overall maximum
        // path sum including the current node
        maxi[0] = Math.max(maxi[0], leftMaxPath + rightMaxPath + root.data);

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

    // Function to find the maximum
    // path sum for the entire binary tree
    public int maxPathSum(TreeNode root) {
        // Initialize maxi to the
        // minimum possible integer value
        int[] maxi = {Integer.MIN_VALUE};

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

        // Return the final maximum path sum
        return maxi[0];
    }

    public static void main(String[] args) {
        // 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 = new Solution();

        // Finding and printing the maximum path sum
        int maxPathSum = solution.maxPathSum(root);
        System.out.println("Maximum Path Sum: " + maxPathSum);
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findMaxPathSum(self, root, maxi):
        # Base case: If the current node is null, return 0
        if not root:
            return 0

        # Calculate the maximum path sum
        # for the left and right subtrees
        leftMaxPath = max(0, self.findMaxPathSum(root.left, maxi))
        rightMaxPath = max(0, self.findMaxPathSum(root.right, maxi))

        # Update the overall maximum
        # path sum including the current node
        maxi[0] = max(maxi[0], leftMaxPath + rightMaxPath + root.val)

        # Return the maximum sum considering
        # only one branch (either left or right)
        # along with the current node
        return max(leftMaxPath, rightMaxPath) + root.val

    def maxPathSum(self, root):
        # Initialize maxi to the
        # minimum possible integer value
        maxi = [float('-inf')]

        # Call the recursive function to
        # find the maximum path sum
        self.findMaxPathSum(root, maxi)

        # Return the final maximum path sum
        return maxi[0]

# Creating a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.right.right = TreeNode(6)
root.left.right.right.right = TreeNode(7)

# Creating an instance of the Solution class
solution = Solution()

# Finding and printing the maximum path sum
maxPathSum = solution.maxPathSum(root)
print("Maximum Path Sum:", maxPathSum)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null){
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

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

        // Calculate the maximum path sum
        // for the left and right subtrees
        const leftMaxPath = Math.max(0, this.findMaxPathSum(root.left, maxi));
        const rightMaxPath = Math.max(0, this.findMaxPathSum(root.right, maxi));

        // Update the overall maximum
        // path sum including the current node
        maxi[0] = Math.max(maxi[0], leftMaxPath + rightMaxPath + root.data);

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

    // Function to find the maximum
    // path sum for the entire binary tree
    maxPathSum(root) {
        // Initialize maxi to the
        // minimum possible integer value
        const maxi = [-Infinity];

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

        // Return the final maximum path sum
        return maxi[0];
    }
}

// Creating a sample binary tree
const 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
const solution = new Solution();

// Finding and printing the maximum path sum
const maxPathSum = solution.maxPathSum(root);
console.log("Maximum Path Sum:", maxPathSum);

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

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code