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 - LeetCode Solution

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

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. The algorithm updates a global maximum path sum considering the sum of the node's value plus both left and right gains (representing a path passing through the node). It then returns to the parent the node's value plus the maximum of left or right gain, representing the best path extending upward. This approach ensures each node is visited once, and all path sums are considered efficiently.

Optimal Approach

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.

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

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

1class Solution {
2    private int res;
3
4    public int maxPathSum(TreeNode root) {
5        res = root.val;
6        dfs(root);
7        return res;
8    }
9
10    private int dfs(TreeNode node) {
11        if (node == null) {
12            return 0;
13        }
14
15        int leftMax = dfs(node.left);
16        int rightMax = dfs(node.right);
17
18        leftMax = Math.max(leftMax, 0);
19        rightMax = Math.max(rightMax, 0);
20
21        res = Math.max(res, node.val + leftMax + rightMax);
22
23        return node.val + Math.max(leftMax, rightMax);
24    }
25}

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

7if not root:
8    return 0

Objective

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

Key Insight

Null nodes represent the absence of a subtree and contribute no gain to the path sum. Returning zero ensures that the recursion terminates correctly and that null children do not negatively affect the path sum calculations.

Interview Quick-Check

Core Logic

Returning zero for null nodes prevents null references and correctly models the absence of contribution from missing children.

State & Boundaries

This base case stops recursion and defines the boundary condition for the DFS.

3

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

10left_max = dfs(root.left)
11right_max = dfs(root.right)
13left_max = max(left_max, 0)
14right_max = max(right_max, 0)

Objective

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

Key Insight

Negative path sums reduce the total gain, so clamping them to zero effectively excludes those subtrees from the path. This ensures that only positive contributions are considered when calculating the maximum path sum through the current node.

Interview Quick-Check

Core Logic

Clamping negative gains to zero ensures the path sum is maximized by excluding subtrees that would decrease the total.

Common Pitfalls & Bugs

Failing to clamp negative gains can lead to suboptimal path sums and incorrect global maximum updates.

4

Update Global Maximum with Path Sum Passing Through Current Node

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

Objective

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

Key Insight

The path passing through the current node can include both left and right subtrees, forming a 'peak' in the path. This sum represents the maximum path sum with the current node as the highest point. Updating the global maximum here ensures all possible paths are considered.

Interview Quick-Check

Core Logic

Updating the global maximum with the sum of node value and both child gains captures paths that branch through the current node.

State & Boundaries

This update happens after computing child gains and before returning to the parent.

5

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

18	`return root.val + max(left_max, right_max)`

Objective

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.

Key Insight

A path extending upward to the parent can only include one subtree (left or right), so the algorithm returns the maximum gain from either side plus the node's value. This return value enables the parent to consider extending the path through this node.

Interview Quick-Check

Core Logic

Returning the node value plus the maximum child gain correctly models the best path extending upward.

Common Pitfalls & Bugs

Returning the sum of both children would incorrectly allow paths to branch upward, violating the path definition.

6

Invoke DFS on Root and Return Global Maximum Path Sum

20dfs(root)
21return res

Objective

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

Key Insight

Calling DFS on the root triggers the entire post-order traversal, ensuring all nodes are processed. Returning the global maximum after traversal completes provides the final answer to the problem.

Interview Quick-Check

Core Logic

Starting DFS at the root ensures the entire tree is explored and all path sums are considered.

State & Boundaries

Returning the global maximum after DFS completes gives the maximum path sum over all possible paths.

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.

Line 13 Critical

left_max = max(left_max, 0)

Clamp left gain to zero if negative.

Negative gains reduce the total path sum, so treating them as zero excludes harmful subtrees, maximizing the path sum.

Line 14 Critical

right_max = max(right_max, 0)

Clamp right gain to zero if negative.

Same reasoning as left gain clamping; ensures only positive contributions are considered.

Line 3 Core

res = root.val

Initialize the global maximum path sum with the root's value.

Starting with the root's value ensures the global maximum is valid even if all other paths have lower sums, and it provides a baseline for comparison during recursion.

Line 8 Core

return 0

Return zero gain for null nodes.

Null nodes contribute no value to the path sum, so returning zero correctly models their absence.

Line 10 Core

left_max = dfs(root.left)

Recursively compute maximum gain from the left child.

Post-order traversal requires computing child gains before processing the current node, enabling correct aggregation of path sums.

Line 11 Core

right_max = dfs(root.right)

Recursively compute maximum gain from the right child.

Symmetric to left child, ensures both subtrees are explored before current node processing.

Line 21 Core

return res

Return the global maximum path sum after traversal.

After DFS completes, the global maximum holds the highest path sum found anywhere in the tree, which is the problem's answer.

Line 5 Core

def dfs(root):

Define the recursive DFS function to compute maximum gains.

Encapsulating the logic in a helper function allows clean recursive traversal and state management, essential for post-order computation of subtree gains.

Line 7 Core

if not root:

Check if the current node is null.

This base case prevents null pointer errors and defines the termination condition for recursion.

Line 20 Core

dfs(root)

Start DFS traversal from the root node.

Invoking DFS on the root triggers the full exploration of the tree, ensuring all paths are evaluated.

Test Your Understanding

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

Because including a negative gain would reduce the overall path sum, it is better to exclude that subtree by treating its contribution as zero, ensuring the path sum is maximized.

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	`private int res;`
3
4	`public int maxPathSum(TreeNode root) {`
5	`res = root.val;`
6	`dfs(root);`
7	`return res;`
8	`}`
9
10	`private int dfs(TreeNode node) {`
11	`if (node == null) {`
12	`return 0;`
13	`}`
14
15	`int leftMax = dfs(node.left);`
16	`int rightMax = dfs(node.right);`
17
18	`leftMax = Math.max(leftMax, 0);`
19	`rightMax = Math.max(rightMax, 0);`
20
21	`res = Math.max(res, node.val + leftMax + rightMax);`
22
23	`return node.val + Math.max(leftMax, rightMax);`
24	`}`
25	`}`

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Global Maximum and Define Recursive DFS to Compute Max Gains

Handle Null Nodes by Returning Zero Gain

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

Update Global Maximum with Path Sum Passing Through Current Node

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

Invoke DFS on Root and Return Global Maximum Path Sum

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.