LeetEye LeetEye
Medium Tree Traversal ~5 min

Binary Tree Maximum Path Sum

trees binary-tree-maximum-path-sum

Problem

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
Path 2 -> 1 -> 3 has sum 6.
Example 2
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Path 15 -> 20 -> 7 has sum 42.
Key Insight

At each node, compute two things: (1) path sum including both children (potential answer), (2) max single-branch sum to return to parent.

At each node: turn-sum = node + left + right (update global max). Return node + max(left, right) (one direction to parent). Ignore negative contributions.

How to Approach This Problem

Pattern Recognition: When you see keywords like binary tree maximum path sum trees, think Tree Traversal.

Step-by-Step Reasoning

1 A valid path in this problem:
Answer: Can start and end anywhere
A path is any connected sequence. It can be entirely in a subtree.
2 A path can "turn" at node X, meaning:
Answer: It includes both left and right children of X
Path goes through left subtree, through X, and through right subtree.
3 When returning a value to parent, we can include:
Answer: At most one child's path
A path can't branch. If we go to parent, we came from one direction only.
4 At each node, we compute two things:
Answer: Turn-sum (global update) and straight-sum (return)
Turn-sum includes both children (potential answer). Straight-sum is what we can extend upward.
5 If a child's contribution is negative:
Answer: Treat it as 0 (don't include it)
A negative contribution makes the path worse. Better to not include that subtree.
6 For a null node, the contribution is:
Answer: 0
No node = no contribution. Neutral value is 0.

Solution

def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')
    
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        
        # Get max gain from children (ignore negative)
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        
        # Path sum if we "turn" at this node
        path_sum = node.val + left_gain + right_gain
        max_sum = max(max_sum, path_sum)
        
        # Return max gain we can extend to parent
        return node.val + max(left_gain, right_gain)
    
    dfs(root)
    return max_sum

Complexity Analysis

Time O(n)
Space O(h)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye