Binary Tree Maximum Path Sum

LeetCode 124: Binary Tree Maximum Path Sum Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a recursive postorder traversal to calculate the maximum path sum rooted at every node while simultaneously updating a global maximum, handling negative values by clamping subtree contributions to zero.

The LeetCode 124 problem, "Binary Tree Maximum Path Sum," asks us to find the maximum sum of a path in a binary tree. A path is defined as any sequence of nodes connected by edges where no node appears more than once. Crucially, the path does not need to pass through the root, and the tree may contain nodes with negative values. This is a popular interview question because it tests the ability to manage global state within a recursive tree traversal.

Brute Force Approach for Binary Tree Maximum Path Sum

A naive approach attempts to treat every single node in the tree as the "highest" node (or anchor) of a potential path.

1. Traverse every node in the tree (e.g., using BFS or DFS).
2. For each node $u$, calculate the maximum path sum that passes through $u$ and extends into its left and right subtrees.
3. To do this, we would need a helper function that computes the maximum path sum starting from a specific node and going downwards.
4. Track the maximum value found across all nodes.

Pseudo-code:

max_global = -infinity

function solve(root):
    if root is null return
    
    // Calculate max path centered at current root
    current_path_sum = root.val + max_down_path(root.left) + max_down_path(root.right)
    max_global = max(max_global, current_path_sum)
    
    solve(root.left)
    solve(root.right)

function max_down_path(node):
    // Recursively find max path going down one branch
    if node is null return 0
    return node.val + max(max_down_path(node.left), max_down_path(node.right))

Why it fails: This approach has a time complexity of $O(N^2)$ in the worst case (a skewed tree). For every node visited in solve, we trigger max_down_path, which re-visits the subtrees. Given the constraint of $3 \times 10^4$ nodes, an $O(N^2)$ solution performs roughly $10^9$ operations, resulting in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

We implement a Depth-First Search (DFS) helper function that returns the maximum "extendable" path sum.

1. Global State: Maintain a variable max_path_sum initialized to negative infinity to track the overall answer.
2. Base Case: If the current node is null, return 0.
3. Recursive Step (Postorder):
   • Recursively call the function on the left child. Store the result in left_gain. Use max(0, result) to ignore negative paths.
   • Recursively call the function on the right child. Store the result in right_gain. Use max(0, result) to ignore negative paths.
4. Local Decision (The Split):
   • Calculate the path sum through the current node: current_path_sum = node.val + left_gain + right_gain.
   • Update max_path_sum with current_path_sum.
5. Return to Parent:
   • Return node.val + max(left_gain, right_gain). This represents the maximum path sum including the current node and at most one of its subtrees.

Execution Flow

Let's trace the execution for root = [-10, 9, 20, null, null, 15, 7].

1. Initialize: max_sum = -infinity. Call dfs(-10).
2. Node -10: Calls dfs(9) and dfs(20).
3. Node 9 (Leaf):
   • Left/Right children return 0.
   • Updates max_sum to 9 (0 + 0 + 9).
   • Returns 9.
4. Node 20: Calls dfs(15) and dfs(7).
   • Node 15 (Leaf): Returns 15. Updates max_sum to 15.
   • Node 7 (Leaf): Returns 7.
5. Back at Node 20:
   • left_gain = 15, right_gain = 7.
   • Split Sum: 15 + 7 + 20 = 42.
   • Update max_sum to 42.
   • Return: 20 + max(15, 7) = 35.
6. Back at Node -10 (Root):
   • left_gain = 9 (from step 3).
   • right_gain = 35 (from step 5).
   • Split Sum: 9 + 35 + (-10) = 34.
   • max_sum remains 42 (since 34 < 42).
   • Returns (-10) + 35 = 25 (ignored as recursion ends).
7. Result: Return max_sum (42).

Proof of Correctness

The correctness relies on the fact that every possible path in a binary tree has a unique "highest" node (the node closest to the root). Our algorithm visits every node via DFS. At each node $u$, we calculate the maximum path sum where $u$ is the highest node by summing $u.val$ plus the maximum positive contributions from its left and right subtrees. Since we iterate through every node and treat it as the potential highest node of the optimal path, we are guaranteed to find the global maximum. The postorder traversal ensures that when we process node $u$, we already have the optimal "extendable" path sums from its children.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly reusable. The core logic of processing children first and then using that data to compute the current node's state appears in several problems:

• LeetCode 104: Maximum Depth of Binary Tree - Returns 1 + max(left, right) to parent.
• LeetCode 110: Balanced Binary Tree - Checks height difference between left and right children post-recursion.
• LeetCode 145: Binary Tree Postorder Traversal - The fundamental traversal mechanism used here.
• LeetCode 337: House Robber III - Returns two values (robbed vs. not robbed) from children to make a decision at the current node.

Reference Implementation

C++ Solution for LeetCode 124

1#include <algorithm>
2#include <climits>
3
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14private:
15    int max_sum;
16
17    int calculateMaxGain(TreeNode* node) {
18        if (!node) return 0;
19
20        // Recursively calculate max gain from left and right subtrees.
21        // If the gain is negative, we ignore it (max with 0).
22        int left_gain = std::max(calculateMaxGain(node->left), 0);
23        int right_gain = std::max(calculateMaxGain(node->right), 0);
24
25        // Calculate the path sum where 'node' is the highest point (split point)
26        int current_path_sum = node->val + left_gain + right_gain;
27
28        // Update the global maximum
29        max_sum = std::max(max_sum, current_path_sum);
30
31        // Return the max gain extendable to the parent
32        return node->val + std::max(left_gain, right_gain);
33    }
34
35public:
36    int maxPathSum(TreeNode* root) {
37        max_sum = INT_MIN;
38        calculateMaxGain(root);
39        return max_sum;
40    }
41};

Java Solution for LeetCode 124

1class Solution {
2    private int maxSum;
3
4    public int maxPathSum(TreeNode root) {
5        maxSum = Integer.MIN_VALUE;
6        calculateMaxGain(root);
7        return maxSum;
8    }
9
10    private int calculateMaxGain(TreeNode node) {
11        if (node == null) {
12            return 0;
13        }
14
15        // Recursively get the max gain from left and right subtrees
16        // Use Math.max(0, ...) to ignore negative path sums
17        int leftGain = Math.max(calculateMaxGain(node.left), 0);
18        int rightGain = Math.max(calculateMaxGain(node.right), 0);
19
20        // Compute the price of the new path where 'node' is the highest point
21        int priceNewPath = node.val + leftGain + rightGain;
22
23        // Update global maximum
24        maxSum = Math.max(maxSum, priceNewPath);
25
26        // Return the max gain the node and one of its subtrees can add to the parent
27        return node.val + Math.max(leftGain, rightGain);
28    }
29}

Python Solution for LeetCode 124

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def maxPathSum(self, root: Optional[TreeNode]) -> int:
9        self.max_sum = float('-inf')
10        
11        def calculate_max_gain(node):
12            if not node:
13                return 0
14            
15            # Recursively get max gain from subtrees
16            # Clamp to 0 if the subtree path sum is negative
17            left_gain = max(calculate_max_gain(node.left), 0)
18            right_gain = max(calculate_max_gain(node.right), 0)
19            
20            # Calculate path sum passing through current node (split point)
21            current_path_sum = node.val + left_gain + right_gain
22            
23            # Update global maximum
24            self.max_sum = max(self.max_sum, current_path_sum)
25            
26            # Return max gain extendable to parent
27            return node.val + max(left_gain, right_gain)
28            
29        calculate_max_gain(root)
30        return self.max_sum