Binary Tree Maximum Path Sum

class Solution {
public:
    int findMaxPath(TreeNode* node) {
        highestSum = INT_MIN;
        calculateMaxSubtreeSum(node);
        return highestSum;
    }

private:
    int highestSum;
    int calculateMaxSubtreeSum(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int leftMax = max(calculateMaxSubtreeSum(node->left), 0);
        int rightMax = max(calculateMaxSubtreeSum(node->right), 0);
        highestSum = max(highestSum, leftMax + rightMax + node->val);
        return max(leftMax + node->val, rightMax + node->val);
    }
};

The solution involves calculating the maximum path sum in a binary tree where the path may start and end at any node. This is done using a C++ class named Solution with a recursive helper function.

• The class has two primary components:

  • findMaxPath(TreeNode* node) - Public member function that initializes the highestSum to the smallest integer possible using INT_MIN. It then calls the recursive helper function calculateMaxSubtreeSum(node) and returns the maximum path sum found.

  • calculateMaxSubtreeSum(TreeNode* node) - Private member function that recursively calculates the maximum sum of any path in the subtree rooted at the provided node. It returns the maximum path sum that includes the current node at its top:

    • Base Case: If the node is null, it returns 0, since an empty tree has a path sum of 0.
    • Recursive Case: The function calculates the maximum path sums of the left and right child subtrees. It ensures that negative path sums do not decrease the overall maximum path sum by using the max function with 0.
    • The function updates highestSum to the maximum of its current value or the sum of the node's value and the maximum path sums from both child subtrees.
    • It returns the maximum value between the node's value plus either the left or right subtree's maximum sum, ensuring the continuation of the potential maximum path towards the parent node.

Through these functions, the solution efficiently finds the maximum path sum by avoiding paths that would decrease the sum due to negative values and continuously keeping track of the highest sum found during the recursion.

class Solution {
    public int maximumPathSum(TreeNode node) {
        highestSum = Integer.MIN_VALUE;
        sumFromNode(node);
        return highestSum;
    }

    private int highestSum;

    private int sumFromNode(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftGain = Math.max(sumFromNode(node.left), 0);
        int rightGain = Math.max(sumFromNode(node.right), 0);

        highestSum = Math.max(highestSum, leftGain + rightGain + node.val);

        return Math.max(leftGain + node.val, rightGain + node.val);
    }
}

The given Java solution tackles the problem of finding the maximum path sum in a binary tree. In this problem, a path is defined as a sequence of nodes where each successive node is directly connected. Notably, the path doesn't need to pass through the root, and it can start and end at any node.

Review this breakdown to understand the structure and function of the code:

• The maximumPathSum(TreeNode node) method serves as the entry point and initializes highestSum with the smallest integer value. It calls sumFromNode(node) to compute the highest path sum possible and returns this value.

• highestSum is a private instance variable used to store the maximum path sum found during the traversal of the tree.

• The recursive method sumFromNode(TreeNode node) calculates the maximum gain from either side of the given node and uses zero as a lower bound to ignore negative path sums. It calculates the potential maximum path sum including both children and the current node's value, updating highestSum if this sum is greater than any previously found.

• The calculation for return value in sumFromNode ensures that for each node processed, the maximum sum involving either the left child or the right child (whichever is greater) plus the node's own value is returned. This aids in propagating the maximum gain up to the caller (either another recursive call or the initial call from maximumPathSum).

Remember, for optimal tree traversal performance and memory use, the implementation effectively utilizes recursion, with each call evaluating node contributions from the bottom of the tree upwards. This ensures that each node's maximum gain in context of its available children is considered, leading to an accurate global maximum across all evaluated paths.

int maximum(int x, int y) { return (x > y) ? x : y; }
int calculateGain(struct TreeNode* node, int* highestSum) {
    if (node == NULL) return 0;
    int leftGain = maximum(0, calculateGain(node->left, highestSum));
    int rightGain = maximum(0, calculateGain(node->right, highestSum));
    *highestSum = maximum(*highestSum, leftGain + rightGain + node->val);
    return maximum(leftGain + node->val, rightGain + node->val);
}
int findMaxPathSum(struct TreeNode* node) {
    int maxResult = INT_MIN;
    calculateGain(node, &maxResult);
    return maxResult;
}

The provided solution in C addresses a common problem in binary tree data structures: finding the maximum path sum. The maximum path sum is the highest sum of node values starting from any node and ending at any node in the tree, where the path doesn't need to pass through the root.

Overview of the Code Structure:

• The maximum function is a straightforward utility to find the maximum of two integers.
• The calculateGain function recursively traverses the binary tree. It calculates maximum path sums from the leaf towards the root, ensuring at each step that negative path sums are not considered (by comparing with 0). This function also updates the maximum path sum found during the traversal.
• The main function, findMaxPathSum, initializes a variable to store the maximum result found, invokes calculateGain, and then returns the maximum path sum.

How the Code Works:

1. Start with defining the maximum function to compare any two integers and return the greater value.
2. Develop the calculateGain function to:
   • Return 0 if the current tree node is NULL, ensuring the termination of recursion.
   • Recursively find the maximum sum for both left and right subtrees. The recursion ensures that every node in the tree is considered.
   • Avoid accumulating negative sums by using the maximum function compared with 0.
   • Update the highest sum recorded using another call to maximum that includes the current node's value and the best gains from left and right subtrees.
   • Resolve the maximum path sum for the sub-tree with the current node as the root.
3. Finally, implement the findMaxPathSum which initializes the maximum result as the smallest integer and starts the recursive calculation.

Conclusion:

This code efficiently calculates the maximum path sum in a binary tree by leveraging a helper function that uses recursive depth-first traversal. It ensures that only paths with positive contributions are considered, maximizing the computed path sum using local comparisons at each node, and updating a global sum that tracks the highest value found across all paths. This method efficiently handles the complexities of varying tree structures and data distributions.

function calculateMaxSum(root) {
    let maximumSum = -Infinity;

    function computeMaxGainLeftRight(node) {
        if (!node) return 0;

        let leftGain = Math.max(computeMaxGainLeftRight(node.left), 0);
        let rightGain = Math.max(computeMaxGainLeftRight(node.right), 0);

        maximumSum = Math.max(maximumSum, leftGain + rightGain + node.val);

        return Math.max(leftGain + node.val, rightGain + node.val);
    }
    computeMaxGainLeftRight(root);
    return maximumSum;
}

The provided JavaScript solution is designed to find the maximum path sum in a binary tree. The path may start and end at any node. In this implementation:

• The calculateMaxSum function is the main function where the computation starts. It initializes maximumSum to negative infinity to handle cases where the tree contains all negative values.

• Inside the main function, a nested helper function computeMaxGainLeftRight is declared. This recursive function is responsible for exploring each node of the binary tree and calculating the gain from each subtree that maximizes the path value using only one side of it (either left or right).

• The recursion evaluates the left and right side gains of each node. The maximum gain for each side is calculated as the maximum value between the recursive call for that side and zero. This ensures that only positive contributions to the sum are considered.

• The maximum path sum that passes through the node and includes both left and right children contributions is updated in maximumSum if it proves to be larger than the current maximumSum.

• The recursion returns the maximum gain including the current node's value plus either the left or right maximum gain, whichever is larger. This value represents the maximum sum from the subtree rooted at the current node that can be included in some larger path.

• After recursion completes on root, the calculateMaxSum function returns the maximumSum, which gives the maximum path sum found in the binary tree.

Use this function by calling calculateMaxSum with the tree's root node as an argument, and it will return the maximum path sum.

class Solution:
    def findMaxSum(self, root: Optional[TreeNode]) -> int:
        maximumPathSum = -float("inf")

        def calculateMaxGain(node: Optional[TreeNode]) -> int:
            nonlocal maximumPathSum

            if not node:
                return 0

            leftGain = max(calculateMaxGain(node.left), 0)
            rightGain = max(calculateMaxGain(node.right), 0)

            maximumPathSum = max(maximumPathSum, leftGain + rightGain + node.val)

            return max(leftGain + node.val, rightGain + node.val)

        calculateMaxGain(root)
        return maximumPathSum

The solution finds the maximum path sum in a binary tree, where a path is defined as any sequence of nodes from any 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.

• The problem is implemented in Python using a class named Solution with a function findMaxSum.
• This function accepts a root of the binary tree and returns an integer representing the maximum path sum.
• The main logic utilizes a helper function calculateMaxGain defined inside findMaxSum.
• The helper function calculates the maximum gain from any node, which is the maximum sum of the node's value and the maximum path sums from its left and right children that do not form a fork (i.e., paths that start at the node and go downwards).
• For each node, it considers two scenarios:
  1. The node is the highest point of the fork in the path, combining the maximum gains from both children and the node's value.
  2. The node is part of a linear path, continuing from either its left or right child.
• Keep track of the global maximum path sum using a nonlocal variable maximumPathSum, updating it with the computed path sums from both scenarios.
• If a node is None, it contributes 0 to the path sum (base case for recursion).
• The function initiates the recursive computation with the root and returns the maximum path sum recorded.

Essentially, the algorithm efficiently calculates and updates the potential maximum sums at each node in a bottom-up manner, ensuring the maximum sum for any path configuration involving partial or full paths through nodes is captured. This recursive dynamic approach guarantees that all potential high-sum configurations are evaluated without redundant calculations, leveraging the benefits of avoiding negative contributions through the use of max(calculateMaxGain(node.left), 0) and similar constructions for right children.