Binary Tree Maximum Path Sum

Find the maximum path sum in a binary tree.

Pattern

Post-order DFS

This problem follows the Post-order DFS pattern, commonly found in the Trees category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

At each node, compute max single-path sum. Update global max with left + node + right.

Key Insight

The 'split' vs 'continue' distinction: update the global max with the full path (left + node + right), but return only one side to the parent.

Step-by-step

1Use post-order DFS (process children before parent)
2At each node, compute the max gain from the left and right subtrees
3Clamp negative gains to 0 (don't take a path with negative sum)
4Update global max with left + node.val + right (path through node)
5Return node.val + max(left, right) to the parent (single path up)

Pseudocode

maxSum = -infinity
def dfs(node):
    if not node: return 0
    left = max(0, dfs(node.left))
    right = max(0, dfs(node.right))
    maxSum = max(maxSum, left + node.val + right)
    return node.val + max(left, right)
dfs(root)
return maxSum

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

Master this pattern with YeetCode

Practice Binary Tree Maximum Path Sum and similar Trees problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Validate Binary Search Tree NextSerialize and Deserialize Binary Tree →