124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum#

Difficulty: Hard

Link to Problem: To see the Binary Tree Maximum Path Sum problem on LeetCode, click here!

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.

Constraints:

The number of nodes in the tree is in the range \([1, 3*10^4]\).
-1000 <= Node.val <= 1000

Probelm Explanation:#

The problem is to find the maximum path sum in a binary tree. 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. The path sum of a path is the sum of the node values in that path.

In this problem, you are given the root of a binary tree, and you need to find the maximum path sum among all possible paths in the tree. Note that the path does not need to start at the root node or end at a leaf node; it can start and end at any nodes in the tree.

To find the maximum path sum, you need to consider both left and right subtrees of each node while traversing the tree. At each node, you have two choices:

Include the current node in the path: In this case, you add the value of the current node to the sum and continue exploring both the left and right subtrees for possible extensions of the path.
Start a new path from the current node: In this case, you do not include the current node in the path sum, and you choose either the left subtree or the right subtree to start a new path.

To solve this problem, you can use a recursive approach to traverse the binary tree. For each node, you calculate the maximum path sum that can pass through that node (option 1) and also return the maximum path sum that can be extended from that node (option 2). You keep track of the global maximum path sum encountered during the traversal.

Ultimately, the maximum path sum among all paths in the tree will be the maximum of the global maximum path sum and the maximum path sum calculated for each node.

The constraints for this problem include:

The number of nodes in the tree is in the range \([1, 3 * 10^4]\).
Node values are in the range [-1000, 1000].

By considering all possible paths through the tree, the algorithm aims to find the most significant sum of node values in any path in the binary tree.

Solution:#

Here’s a Python function to implement this algorithm:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root):
        def max_path_sum_helper(node):
            if not node:
                return 0
            
            # Recursively calculate the maximum path sum for left and right subtrees
            left_max = max(0, max_path_sum_helper(node.left))
            right_max = max(0, max_path_sum_helper(node.right))
            
            # Update the global maximum path sum
            self.max_sum = max(self.max_sum, left_max + right_max + node.val)
            
            # Return the maximum path sum starting from the current node
            return max(left_max, right_max) + node.val
        
        self.max_sum = float('-inf')  # Initialize the global maximum to negative infinity
        max_path_sum_helper(root)  # Start the recursive traversal from the root
        return self.max_sum

Explanation:#

The code starts by defining a TreeNode class to represent nodes in the binary tree. Each TreeNode has a val attribute representing its value, a left attribute pointing to the left child, and a right attribute pointing to the right child.
Next, a Solution class is defined to contain the maxPathSum method, which will be used to find the maximum path sum in the binary tree.
Within the maxPathSum method, a helper function called max_path_sum_helper is defined. This recursive function takes a single argument, node, which is the current node being considered during traversal.
Inside the max_path_sum_helper function:
- If node is None (i.e., the current node is a null node), it returns 0. This is the base case of the recursion.
- It calculates the maximum path sum starting from the left subtree (left_max) and the right subtree (right_max). Importantly, it uses max(0, ...) to ensure that negative values (which would make the path sum smaller) are not considered. If a subtree’s path sum is negative, it’s better to not include it in the path.
- The code then updates the global maximum path sum (self.max_sum) by checking if the sum of left_max, right_max, and the current node’s value is greater than the current maximum.
- Finally, it returns the maximum path sum starting from the current node, which is the maximum of left_max and right_max plus the current node’s value.
Before calling the max_path_sum_helper function, the max_sum attribute of the Solution class is initialized to negative infinity (float('-inf')). This is done to ensure that any valid path sum encountered during traversal will be greater than the initial value of max_sum.
The max_path_sum_helper function is called with the root of the binary tree, effectively starting the traversal from the root node.
Once the traversal is complete, the method returns the value of self.max_sum, which contains the maximum path sum found in the binary tree.
Example usage at the bottom of the code demonstrates how to create binary trees and use the maxPathSum method to find the maximum path sum for two different tree structures.

In summary, the code uses a recursive approach to explore all possible paths in the binary tree, ensuring that negative path sums are not considered. It keeps track of the maximum path sum encountered and returns that maximum value as the result.

Test cases:#

Here’s how you can use this solution:

# Example 1: 

# Example usage:
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
solution = Solution()
print(solution.maxPathSum(root1))

# Example 2:

root2 = TreeNode(-10)
root2.left = TreeNode(9)
root2.right = TreeNode(20)
root2.right.left = TreeNode(15)
root2.right.right = TreeNode(7)
print(solution.maxPathSum(root2))

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the given code:

Time Complexity:

The code uses a recursive depth-first traversal to explore each node in the binary tree exactly once.
During the traversal, for each node, we perform constant time operations, such as updating the max_sum variable and calculating the maximum path sum starting from that node.
Therefore, the time complexity of the code is O(N), where N is the number of nodes in the binary tree.

Space Complexity:

The space complexity of the code is determined by the space used in the call stack during the recursive traversal.
In the worst case, the depth of the call stack can be equal to the height of the binary tree. In an unbalanced tree, this could be O(N), but in a balanced binary tree, the height is O(log N).
Additionally, the code uses a constant amount of space for variables like left_max, right_max, and max_sum.
Therefore, the overall space complexity is O(H), where H is the height of the binary tree. In the worst case, it’s O(N), and in the best case (a balanced binary tree), it’s O(log N).

In summary:

Time Complexity: O(N)
Space Complexity: O(H), where H is the height of the binary tree, ranging from O(log N) to O(N) depending on the tree’s balance.

Challenging Exercises:#

Print the Maximum Path: Modify the code to not only find the maximum path sum but also print the nodes involved in the maximum path. You can print the nodes in the correct order from the root to the leaf.
Path Sum Count: Instead of finding the maximum path sum, find the count of unique paths that sum to a given target value. Each path can start and end anywhere in the tree.