#124

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Maximum Path Sum

Calculate the maximum sum of any path in a binary tree by exploring all node sequences using DFS and dynamic programming.

dynamic programming tree depth first search binary tree

Problem Statement

Given a binary tree, determine the maximum sum achievable by any path connecting nodes where each adjacent pair shares an edge. A node may appear only once in a path, and paths are not required to include the root. Each node's value can be positive or negative, and the tree size may reach up to tens of thousands of nodes.

Return the largest possible sum across all valid paths in the tree. The path sum is defined as the sum of node values along the path. For example, a tree with root [1,2,3] has maximum path 2 -> 1 -> 3 with sum 6, and a tree [-10,9,20,null,null,15,7] has maximum path 15 -> 20 -> 7 with sum 42.

Examples

Example 1

Input: root = [1,2,3]

Output: 6

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

The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints

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

Solution Approach

Depth-First Search with Maximum Path Tracking

Perform a DFS starting at the root, recursively computing the maximum path sum of the left and right subtrees. At each node, calculate the maximum path including the current node as the turning point between left and right children. Update a global maximum to capture the largest path sum seen so far. This ensures that paths not passing through the root are still evaluated and leverages subtree contributions effectively.

State Propagation Using Dynamic Programming

At each node, return the maximum path sum that can be extended to the node’s parent. This involves choosing the larger of the left or right subtree contributions and adding the current node value, discarding negative contributions to avoid reducing the path sum. By storing and propagating these maximum contributions, redundant calculations are avoided and each node’s impact on potential paths is accurately accounted for.

Handling Negative and Mixed Node Values

Nodes may have negative values, so a path that includes them could reduce the sum. Always compare left and right subtree sums with zero before adding the current node’s value to ensure negative paths are ignored in extension. This selective inclusion ensures the global maximum accounts only for profitable paths, preventing suboptimal selections and correctly capturing maximum sums even in trees with mixed positive and negative values.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because each node is visited once during the DFS traversal. The space complexity is O(h) where h is the height of the tree due to the recursive call stack. Both complexities are consistent with traversing all nodes while maintaining state for maximum path sums across the tree.

What Interviewers Usually Probe

Do you account for negative node values when calculating the maximum path sum?
Can you explain how your DFS approach propagates maximum path contributions to the parent nodes?
Will you update the global maximum at each node correctly to include paths crossing through the node?

Common Pitfalls or Variants

Common pitfalls

Forgetting to ignore negative subtree contributions when extending paths to parent nodes, leading to lower sums.
Updating the global maximum only with single child contributions and missing paths through the current node.
Confusing path extension to parent versus path sum including current node, which can incorrectly omit optimal paths.

Follow-up variants

Find maximum path sum where path must start and end at leaf nodes only.
Compute the maximum sum path in a binary tree constrained to paths of length at most k edges.
Determine the maximum path sum in a binary tree when nodes can be revisited at most once.

FAQ

What is a path in Binary Tree Maximum Path Sum?

A path is any sequence of nodes connected by edges, with each node appearing at most once. It does not have to pass through the root, capturing all possible sums.

How do you handle negative values in this problem?

When extending a path to the parent node, ignore negative contributions from subtrees, ensuring that only profitable node values are added to maximize the path sum.

Can the maximum path sum exclude the root?

Yes, the maximum path sum may exist entirely within left or right subtrees without including the root, so every node must consider paths through it independently.

What DFS strategy is effective for this problem?

A post-order DFS is effective, recursively computing maximum contributions from left and right children before updating the global maximum with paths passing through the current node.

Why track state at each node for Binary Tree Maximum Path Sum?

Tracking maximum path sum at each node allows the algorithm to propagate optimal contributions to parent nodes while updating a global maximum, ensuring all paths are considered efficiently.

terminal

Solution

Solution 1: Recursion

When thinking about the classic routine of recursion problems in binary trees, we consider:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            left = max(0, dfs(root.left))
            right = max(0, dfs(root.right))
            nonlocal ans
            ans = max(ans, root.val + left + right)
            return root.val + max(left, right)

        ans = -inf
        dfs(root)
        return ans

Continue Practicing

#337 house robber iii #968 binary tree cameras #129 sum root to leaf numbers