Binary Tree Maximum Path Sum - Python Solution

1. Introduction

The "Binary Tree Maximum Path Sum" problem is a challenging yet interesting problem that deals with finding the maximum sum of values in any path within a binary tree. This path can start and end at any node in the tree and does not necessarily have to pass through the root. Solving this problem involves understanding tree traversal and recursion.

Problem

Given the root of a binary tree, the task is to find the maximum path sum of any non-empty path in the tree. A path is defined as a sequence of nodes where each pair of adjacent nodes has an edge connecting them, and each node appears in the sequence at most once.

2. Solution Steps

1. Traverse the binary tree using recursion.

2. At each node, calculate the maximum path sum passing through that node.

3. The maximum path sum at each node is the node's value plus the maximum path sum of its left and right child nodes.

4. Update the overall maximum path sum during the traversal.

5. Ensure that negative path sums do not reduce the overall maximum.

3. Code Program

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

def maxPathSum(root):
    def maxGain(node):
        nonlocal maxSum
        if not node:
            return 0

        # Max sum on the left and right sub-trees of node
        leftGain = max(maxGain(node.left), 0)
        rightGain = max(maxGain(node.right), 0)

        # Max path sum for the current node
        priceNewpath = node.val + leftGain + rightGain

        # Update maxSum if it's better to start a new path
        maxSum = max(maxSum, priceNewpath)

        # For recursion return the max gain if continue the same path
        return node.val + max(leftGain, rightGain)

    maxSum = float('-inf')
    maxGain(root)
    return maxSum

# Example Usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(maxPathSum(root))

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(maxPathSum(root))

Output:

6
42

Explanation:

1. Recursion Function: The maxGain function computes the maximum path sum starting from the current node and extending to any leaf node.

2. Node Processing: For each node, it calculates the maximum path sum from both left and right children, excluding negative sums.

3. New Path Evaluation: The path sum involving the current node as the highest node is computed and compared with the global maximum.

4. Global Maximum: maxSum keeps track of the highest path sum found during the traversal.

5. Return Value: The function returns the maximum path sum found in the binary tree.