Maximum Path Sum

Find the maximum path sum in a binary tree.

Language Selection

Choose your preferred programming language

Showing: Python

Maximum Path Sum

Problem Statement

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.

Examples

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Example 3:

Input: root = [-3]
Output: -3
Explanation: The optimal path is -3 with a path sum of -3.

Constraints

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

Approach 1: Recursive DFS with Global Maximum (Optimal)

Algorithm

Use recursion to calculate the maximum path sum by considering different path scenarios.

Steps:

For each node, calculate the maximum path sum that includes the node
Consider three cases:
- Path through current node only
- Path through current node and left subtree
- Path through current node and right subtree
Update global maximum if current path is better
Return the maximum path sum that can be extended upward

Implementation

Python:

def maxPathSum(root):
    """
    Find maximum path sum in binary tree using recursive DFS
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    max_sum = [float('-inf')]  # Use list to allow modification in nested function
    
    def dfs(node):
        if not node:
            return 0
        
        # Calculate maximum path sum for left and right subtrees
        left_sum = max(0, dfs(node.left))  # Ignore negative sums
        right_sum = max(0, dfs(node.right))  # Ignore negative sums
        
        # Calculate path sum through current node
        current_sum = node.val + left_sum + right_sum
        
        # Update global maximum
        max_sum[0] = max(max_sum[0], current_sum)
        
        # Return maximum path sum that can be extended upward
        return node.val + max(left_sum, right_sum)
    
    dfs(root)
    return max_sum[0]

Java:

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    /**
     * Find maximum path sum in binary tree using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // Calculate maximum path sum for left and right subtrees
        int leftSum = Math.max(0, dfs(node.left));  // Ignore negative sums
        int rightSum = Math.max(0, dfs(node.right));  // Ignore negative sums
        
        // Calculate path sum through current node
        int currentSum = node.val + leftSum + rightSum;
        
        // Update global maximum
        maxSum = Math.max(maxSum, currentSum);
        
        // Return maximum path sum that can be extended upward
        return node.val + Math.max(leftSum, rightSum);
    }
}

Go:

func maxPathSum(root *TreeNode) int {
    /**
     * Find maximum path sum in binary tree using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    maxSum := math.MinInt32
    
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        
        // Calculate maximum path sum for left and right subtrees
        leftSum := max(0, dfs(node.Left))  // Ignore negative sums
        rightSum := max(0, dfs(node.Right))  // Ignore negative sums
        
        // Calculate path sum through current node
        currentSum := node.Val + leftSum + rightSum
        
        // Update global maximum
        maxSum = max(maxSum, currentSum)
        
        // Return maximum path sum that can be extended upward
        return node.Val + max(leftSum, rightSum)
    }
    
    dfs(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript:

/**
 * Find maximum path sum in binary tree using recursive DFS
 * Time: O(n)
 * Space: O(h) where h is height of tree
 */
function maxPathSum(root) {
    let maxSum = -Infinity;
    
    function dfs(node) {
        if (!node) {
            return 0;
        }
        
        // Calculate maximum path sum for left and right subtrees
        const leftSum = Math.max(0, dfs(node.left));  // Ignore negative sums
        const rightSum = Math.max(0, dfs(node.right));  // Ignore negative sums
        
        // Calculate path sum through current node
        const currentSum = node.val + leftSum + rightSum;
        
        // Update global maximum
        maxSum = Math.max(maxSum, currentSum);
        
        // Return maximum path sum that can be extended upward
        return node.val + Math.max(leftSum, rightSum);
    }
    
    dfs(root);
    return maxSum;
}

C#:

public class Solution {
    private int maxSum = int.MinValue;
    
    /// <summary>
    /// Find maximum path sum in binary tree using recursive DFS
    /// Time: O(n)
    /// Space: O(h) where h is height of tree
    /// </summary>
    public int MaxPathSum(TreeNode root) {
        DFS(root);
        return maxSum;
    }
    
    private int DFS(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // Calculate maximum path sum for left and right subtrees
        int leftSum = Math.Max(0, DFS(node.left));  // Ignore negative sums
        int rightSum = Math.Max(0, DFS(node.right));  // Ignore negative sums
        
        // Calculate path sum through current node
        int currentSum = node.val + leftSum + rightSum;
        
        // Update global maximum
        maxSum = Math.Max(maxSum, currentSum);
        
        // Return maximum path sum that can be extended upward
        return node.val + Math.Max(leftSum, rightSum);
    }
}

Complexity Analysis

Time Complexity: O(n) - Visit each node exactly once
Space Complexity: O(h) - Recursion stack depth equals tree height

Key Insights

Global Maximum: Track the maximum path sum across all possible paths
Path Extension: Return maximum path sum that can be extended upward
Negative Sums: Ignore negative subtree sums (set to 0)
Three Cases: Consider path through node, left subtree, or right subtree
Post-order Traversal: Process children before parent

Edge Cases

Single Node: Handle tree with only one node
All Negative Values: Handle trees with all negative values
Mixed Values: Handle trees with both positive and negative values
Skewed Tree: Handle left-skewed or right-skewed trees
Large Tree: Handle trees with many nodes

Test Cases

def test_maxPathSum():
    # Test case 1: Normal case
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(3)
    
    result1 = maxPathSum(root1)
    assert result1 == 6
    
    # Test case 2: Negative values
    root2 = TreeNode(-10)
    root2.left = TreeNode(9)
    root2.right = TreeNode(20)
    root2.right.left = TreeNode(15)
    root2.right.right = TreeNode(7)
    
    result2 = maxPathSum(root2)
    assert result2 == 42
    
    # Test case 3: Single node
    root3 = TreeNode(-3)
    result3 = maxPathSum(root3)
    assert result3 == -3
    
    # Test case 4: All negative values
    root4 = TreeNode(-1)
    root4.left = TreeNode(-2)
    root4.right = TreeNode(-3)
    
    result4 = maxPathSum(root4)
    assert result4 == -1
    
    print("All tests passed!")

test_maxPathSum()

Follow-up Questions

Maximum Path Sum II: Find maximum path sum in n-ary tree?
Maximum Path Sum with Constraints: Add additional constraints?
Maximum Path Sum with Weights: Handle weighted edges?
Maximum Path Sum with Cycles: Handle cycles in the tree?
Maximum Path Sum with K Nodes: Find maximum path sum with at most k nodes?

Common Mistakes

Not Handling Negative Values: Not considering negative node values
Wrong Path Calculation: Incorrectly calculating path sums
Missing Global Maximum: Not tracking the global maximum
Incorrect Return Value: Not returning the correct value for path extension
Edge Case Handling: Not handling single node or all negative values

Interview Tips

Start with Recursion: Most intuitive approach
Explain Path Scenarios: Show understanding of different path cases
Handle Edge Cases: Mention negative values and single node cases
Discuss Trade-offs: Compare recursive vs iterative approaches
Follow-up Ready: Be prepared for variations and optimizations

Concept Explanations

Maximum Path Sum: We need to find the maximum sum of any path in the tree. A path can start and end at any node, and can go through any number of nodes.

Path Scenarios: For each node, we consider three scenarios:

Path through current node only
Path through current node and left subtree
Path through current node and right subtree

Global Maximum: We maintain a global maximum that tracks the best path sum found so far across all nodes.

Path Extension: For each node, we return the maximum path sum that can be extended upward to the parent node. This is the maximum of the current node’s value plus the maximum of its left and right subtree sums.

Negative Sums: If a subtree has a negative sum, we ignore it (set to 0) because including it would decrease the total path sum.

Why Recursion Works: The problem has a recursive structure - if we can find the maximum path sum in subtrees, we can determine the maximum path sum for the entire tree.

Post-order Traversal: We use post-order traversal because we need to process the children before the parent to calculate the maximum path sums correctly.