roadmap/trees/Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

HardFacebookAmazonGoogleMicrosoft

Problem

Given a binary tree, find the maximum path sum. A path can start and end at any node in the tree.

Intuition — the key insight

Post-order DFS. At each node: the gain from left = max(0, dfs(left)) — ignore negative subtrees. Same for right. The path through this node = node.val + leftGain + rightGain — update global max. But we can only extend upward in ONE direction, so return node.val + max(leftGain, rightGain) to parent.

Approach

DFS with global max

dfs returns the maximum path sum extending from this node upward (can't go both ways). At each node, compute path through this node (both directions) to update global max. Return only the better single direction.

Complexity

Time

O(n)

Space

O(h)

Visit each node once. Stack depth = tree height.

Solution code

Python

def maxPathSum(self, root: TreeNode) -> int:
    self.best = float('-inf')
    
    def dfs(node) -> int:
        if not node: return 0
        
        left  = max(0, dfs(node.left))   # ignore if negative
        right = max(0, dfs(node.right))  # ignore if negative
        
        # Path through this node (update global max)
        self.best = max(self.best, node.val + left + right)
        
        # Return best single-direction extension to parent
        return node.val + max(left, right)
    
    dfs(root)
    return self.best

Edge cases to remember

⚠All negative values: answer is the least negative single node

⚠Single node: return its value

⚠Must initialize best to -infinity, not 0