How do you solve Binary Tree Maximum Path Sum?

Use a recursive DFS function that returns the maximum gain from a node to its parent. At each node, compute left and right gains recursively, clamp negative gains to zero, update a global maximum with the sum of node value plus both gains, and return the node value plus the maximum gain of one subtree. This guarantees O(n) time complexity and O(h) space complexity due to recursion stack, where h is the tree height.

What pattern does Binary Tree Maximum Path Sum use?

The Pattern: DFS (Post-Order Traversal with State Propagation) The Heuristic: When solving tree path sum problems, use post-order DFS to compute maximum gains from children, discard negative contributions, and propagate the best upward path while updating a global maximum that considers paths passing through the current node.

Binary Tree Maximum Path Sum — DFS

Q: What is the time complexity of Binary Tree Maximum Path Sum?

O(n). Each node is visited exactly once in the DFS traversal, and constant work is done per node, resulting in linear time relative to the number of nodes.

Problem

Given the root of a binary tree, return the maximum path sum of any non-empty path, where a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.

The number of nodes in the tree is in the range [1, 3 * 10⁴]
−1000 ≤ Node.val ≤ 1000

Example

Input: root = [-10,9,20,null,null,15,7]

Output: 42

The maximum path sum is obtained by the path 15 -> 20 -> 7, which sums to 42. The algorithm recursively explores each node, calculating the maximum gain from left and right subtrees, ignoring negative gains by treating them as zero. At node 20, left gain is 15, right gain is 7, so the path through 20 yields 20 + 15 + 7 = 42, updating the global maximum. The recursion returns the maximum gain from either left or right subtree plus the node's value to its parent, enabling the parent to consider paths extending through this node.

Approach

Straightforward Solution

A brute-force approach would consider all possible paths by enumerating every node and every possible path through it, resulting in exponential time complexity due to overlapping subproblems and repeated calculations.

Core Observation

The maximum path sum can be decomposed into subproblems where each node contributes its value plus the maximum gain from either left or right subtree, but the path can also include both subtrees if the node acts as a 'peak'. Negative gains reduce the sum and should be discarded by treating them as zero.

Path to Optimal

Preview

The key insight is to use a post-order DFS traversal to compute, for each node, the maximum gain from its left and right children, ignoring negative gains by replacing them with zero…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS function that returns the maximum gain from a node to its parent…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once in the DFS traversal, and constant work is done per node, resulting in linear time relative to the number of nodes.

Space

O(h)

The recursion stack depth is proportional to the height of the tree, which is O(h). No additional significant data structures are used.

Solution

Python

1class Solution:
  def maxPathSum(self, root: TreeNode) -> int:
      res = root.val
4
      def dfs(root):
          nonlocal res
          if not root:
              return 0
          
          left_max = dfs(root.left)
          right_max = dfs(root.right)
          
          left_max = max(left_max, 0)
          right_max = max(right_max, 0)
15
          res = max(res, root.val + left_max + right_max)
17
          return root.val + max(left_max, right_max)
19
      dfs(root)
      return res

Step-by-Step Solution

1

Initialize Global Maximum and Define Recursive DFS to Compute Max Gains

3res = root.val
5def dfs(root):
6    nonlocal res

Objective

To set up a global variable to track the maximum path sum and define a recursive function that computes the maximum gain from each node to its parent.

Key Insight

A global variable allows the algorithm to track the best path sum found anywhere in the tree during recursion. The recursive DFS function explores the tree in post-order, ensuring that the maximum gains from left and right children are computed before processing the current node. This setup is essential to propagate correct state upward and update the global maximum accurately.

Interview Quick-Check

Core Logic

The global maximum stores the best path sum found so far, while the DFS function returns the maximum gain from a node to its parent, enabling the parent to consider extending the path.

State & Boundaries

The DFS uses post-order traversal to ensure child gains are computed before the current node's calculations.

Common Pitfalls & Bugs

Forgetting to declare the global variable as nonlocal inside the DFS function leads to incorrect updates.

2

Handle Null Nodes by Returning Zero Gain

To define the base case of the recursion by returning zero when encountering a null node.

3

Compute Maximum Gains from Left and Right Subtrees, Clamping Negatives to Zero

To recursively compute the maximum gain from left and right children, ignoring negative gains by replacing them with zero.

4

Update Global Maximum with Path Sum Passing Through Current Node

To update the global maximum path sum by considering the sum of the current node's value plus both left and right maximum gains.

5

Return Maximum Gain to Parent by Adding Node Value to Larger Child Gain

To return the maximum gain from the current node to its parent, which is the node's value plus the larger of the left or right gains.

6

Invoke DFS on Root and Return Global Maximum Path Sum

To start the recursive DFS traversal from the root and return the computed global maximum path sum.

5 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 16 Critical

res = max(res, root.val + left_max + right_max)

Update global maximum with the sum of node value and both child gains.

This line captures the maximum path sum passing through the current node, considering both subtrees as branches, which is critical to find the overall maximum path.

Line 18 Critical

return root.val + max(left_max, right_max)

Return the node value plus the larger child gain to the parent.

Returning only one subtree's gain plus the node value ensures the path remains a valid sequence without branching upward, preserving the path definition.

Line 6 Critical

nonlocal res

Declare the global maximum variable as nonlocal to allow updates inside DFS.

Without declaring nonlocal, updates to the global maximum inside DFS would create a local variable, preventing correct tracking of the maximum path sum.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why do we clamp negative gains to zero when calculating the maximum gain from a subtree?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Binary Tree Maximum Path Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Binary Tree Maximum Path Sum drill

or drill a free problem

1	`class Solution:`
2	`def maxPathSum(self, root: TreeNode) -> int:`
3	`res = root.val`
4
5	`def dfs(root):`
6	`nonlocal res`
7	`if not root:`
8	`return 0`
9
10	`left_max = dfs(root.left)`
11	`right_max = dfs(root.right)`
12
13	`left_max = max(left_max, 0)`
14	`right_max = max(right_max, 0)`
15
16	`res = max(res, root.val + left_max + right_max)`
17
18	`return root.val + max(left_max, right_max)`
19
20	`dfs(root)`
21	`return res`