124. Binary Tree Maximum Path Sum

Introduction

The "Binary Tree Maximum Path Sum" problem asks to find the maximum path sum in a binary tree. The path can start and end at any node in the tree, but it must go downward, meaning the path can only travel from parent to child nodes. This problem is a typical example of dynamic programming applied to binary trees, and it can be solved using depth-first search (DFS) with a helper function to track the maximum path sum at each node.

Problem Statement

Given the root of a binary tree, return the maximum path sum. A path is defined as any sequence of nodes in the tree where the path must go downwards, meaning it must be directed from parent to child. The sum of a path is the sum of the node values along the path.

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

The tree node structure is given above. We need to find the maximum path sum from any node to any other node in the tree.

Approach

To solve the problem, we perform a depth-first search (DFS) traversal of the tree, calculating the maximum sum we can achieve starting from each node. For each node, we calculate two things:

• The maximum path sum that starts from the current node and extends downward through its left or right child (i.e., the best path sum rooted at this node).
• The maximum path sum that can be obtained by considering the current node as the highest point in the path, which may extend to both the left and right children (i.e., the best path sum that includes both subtrees and the current node).

The final result will be the largest path sum found during the traversal, which will be the global maximum path sum.

Algorithm

The algorithm works as follows:

1. Start by performing a DFS traversal of the tree.
2. At each node, calculate the maximum path sum that starts from this node and extends downward to either its left or right child.
3. Additionally, calculate the maximum path sum that includes both subtrees and the node itself (i.e., the path goes through the node and both its left and right children).
4. Maintain a global variable to store the maximum path sum found so far and update it as necessary.
5. Return the global maximum path sum once the DFS traversal is complete.

The recursive helper function ensures that at each step, we only consider valid downward paths, while also accounting for paths that can go through the current node and extend to both subtrees.

Example

Consider the following binary tree:

             1
            / \
           2   3
          / \
         4   5
        

In this example, the following path sums can be considered: - Path 1: 4 → 2 → 5 (sum = 11) - Path 2: 2 → 5 (sum = 7) - Path 3: 1 → 3 (sum = 4) - Path 4: 1 → 2 → 4 (sum = 7) - Path 5: 1 → 2 → 4 → 5 (sum = 11)

The maximum path sum in this case is 11, which corresponds to the path 4 → 2 → 5.

Code Implementation

Below is the Python implementation of the algorithm to find the binary tree maximum path sum:

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

def maxPathSum(root):
    def dfs(node):
        if not node:
            return 0

        # Recursively calculate the maximum path sum from the left and right subtrees
        left = max(dfs(node.left), 0)  # Ignore negative path sums
        right = max(dfs(node.right), 0)  # Ignore negative path sums

        # Calculate the maximum path sum passing through the current node
        current_max = node.val + left + right

        # Update the global maximum path sum
        maxPathSum.res = max(maxPathSum.res, current_max)

        # Return the maximum path sum starting from the current node
        return node.val + max(left, right)

    # Initialize the global maximum path sum variable
    maxPathSum.res = float('-inf')
    dfs(root)
    return maxPathSum.res
        

In this code: - The `dfs` function performs a depth-first search of the tree. For each node, it computes the maximum path sum starting from that node, considering both the left and right subtrees. - The function also calculates the best path sum that passes through the current node and updates the global maximum path sum if necessary. - The `maxPathSum` variable is used to store the global maximum path sum, which is returned after the traversal.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is visited once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack during the DFS traversal. In the worst case, the height of the tree is O(n) (for a skewed tree), and in the best case, it is O(log n) (for a balanced tree).

Conclusion

The "Binary Tree Maximum Path Sum" problem is an excellent example of dynamic programming applied to binary trees. By using depth-first search (DFS) and keeping track of the maximum path sum at each node, we can efficiently compute the maximum path sum for any binary tree. The problem tests your ability to use recursion and manage global variables to track the maximum value found during a tree traversal.