Binary Tree Maximum Path Sum

How it works

In the maximum path sum problem, a path can start and end anywhere in the tree, but it must go downward at each step (parent → child).

For every node, two values matter:

1. Max Downward Path starting at this node

   • This path can only go to one side (left or right).
   • Used by the parent to extend the path upward.
   • Computed as:

2. Max Path Through This Node

   • This can include both left and right downward paths:

   • This may form the global maximum path.

While computing DFS:

• If a downward path sum is negative, we drop it (take 0), because adding negative values only makes the path worse.
• At each node, update the global maximum using the "path through this node".
• Return the best downward path to the parent.

This ensures each node is visited once — O(n) optimal time.

Steps

1. Maintain a global result res, initialized with the root’s value.
2. Define dfs(node):
   • If node is None, return 0.
   • Recursively compute:

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Initializing Result to Zero Instead of Negative Infinity

When all node values are negative, the maximum path sum is still negative. Initializing the result to 0 causes incorrect answers for trees with all negative values.

Forgetting to Clamp Negative Subtree Contributions to Zero

A subtree with negative sum should not be included in the path. Failing to take max(0, subtree_sum) adds negative values that reduce the total.

Returning the Full Path Sum Instead of Single-Branch Sum

The recursive function must return only one branch (left OR right) to the parent, not both. Returning node.val + leftMax + rightMax allows invalid paths that fork at multiple nodes.

Not Considering Single-Node Paths

A valid path can be just one node. The algorithm must consider node.val alone as a potential maximum, especially when both subtrees contribute negative values.

Confusing Path Sum With Downward Path

The maximum path can go through any node as the "turning point" (left subtree -> node -> right subtree). This is different from paths that only go downward from root to leaf.

from typing import Optional

# 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:
        res = [root.val]

        def dfs(root):
            if not root:
                return 0

            leftMax = dfs(root.left)
            rightMax = dfs(root.right)
            leftMax = max(leftMax, 0)
            rightMax = max(rightMax, 0)

            res[0] = max(res[0], root.val + leftMax + rightMax)
            return root.val + max(leftMax, rightMax)

        dfs(root)
        return res[0]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = root->val;
        dfs(root, res);
        return res;
    }

private:
    int dfs(TreeNode* root, int& res) {
        if (!root) {
            return 0;
        }

        int leftMax = max(dfs(root->left, res), 0);
        int rightMax = max(dfs(root->right, res), 0);

        res = max(res, root->val + leftMax + rightMax);
        return root->val + max(leftMax, rightMax);
    }
};