Binary Tree Maximum Path Sum

Difficulty: Hard Source: NeetCode

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1: Input: root = [1,2,3] Output: 6 Explanation: 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 Explanation: 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 * 10^4]
• -1000 <= Node.val <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Diameter of Binary Tree — Very similar structure: compute gain at each node, track global max
• DFS Post-order — Computing values bottom-up
• Global Max Tracking — The answer isn’t always at the root; track it across all nodes

1. DFS with Global Max

Intuition

This is the classic “gain vs contribution” split. At each node, we think about two things:

1. What’s the maximum path sum that passes through this node (using both subtrees)? This updates the global answer.
2. What’s the maximum contribution this node can make to its parent? A node can only extend a path in one direction to its parent (left or right, not both), and we should ignore negative contributions.

The key insight: gain = node.val + max(left_gain, 0) + max(right_gain, 0) updates the global max, but we return node.val + max(left_gain, right_gain, 0) to the parent (one direction only, and at least 0 since we can always stop).

Algorithm

1. Define dfs(node) returning the max gain this node can contribute upward
2. left_gain = max(dfs(node.left), 0) — ignore negative subtrees
3. right_gain = max(dfs(node.right), 0) — ignore negative subtrees
4. Update global_max = max(global_max, node.val + left_gain + right_gain)
5. Return node.val + max(left_gain, right_gain) — can only go one direction upward

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    global_max = [float('-inf')]  # Use list to allow mutation in nested function

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

        # Max gain from left and right subtrees (ignore if negative)
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)

        # Path through this node (can use both subtrees)
        path_through_node = node.val + left_gain + right_gain
        global_max[0] = max(global_max[0], path_through_node)

        # Return max gain this node can contribute to parent (one direction only)
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return global_max[0]

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, 2, 3])
print(max_path_sum(root1))  # 6  (2 → 1 → 3)

root2 = build_tree([-10, 9, 20, None, None, 15, 7])
print(max_path_sum(root2))  # 42  (15 → 20 → 7)

# All negative: answer is the least negative single node
root3 = build_tree([-3])
print(max_path_sum(root3))  # -3

root4 = build_tree([-1, -2, -3])
print(max_path_sum(root4))  # -1 (just the root)

# Path doesn't go through root
#       -10
#       /  \
#      9    20
#          /  \
#         15   7
# Best path: 15 + 20 + 7 = 42, ignoring -10 entirely

# Mixed: some paths involve going up through a parent
root5 = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1])
print(max_path_sum(root5))  # 48  (7 + 11 + 4 + 5 + 8 + 13)

Complexity

• Time: O(n) — every node is visited once
• Space: O(h) — recursion stack depth

Tracing Through Example 2

Tree: [-10, 9, 20, null, null, 15, 7]

       -10
       /  \
      9    20
          /  \
         15   7

dfs(9) → 9, updates max = 9
dfs(15) → 15, updates max = 15
dfs(7) → 7, updates max = 7
dfs(20):
  left_gain = max(15, 0) = 15
  right_gain = max(7, 0) = 7
  path_through = 20 + 15 + 7 = 42, updates max = 42
  returns 20 + max(15, 7) = 35
dfs(-10):
  left_gain = max(9, 0) = 9
  right_gain = max(35, 0) = 35
  path_through = -10 + 9 + 35 = 34, max stays 42
  returns -10 + max(9, 35) = 25

Final answer: 42 ✓

Common Pitfalls

Not clamping gains at 0. If a subtree has a negative sum, including it only hurts the total. Using max(dfs(child), 0) means we treat negative subtrees as “don’t extend the path here.”

Returning the path-through value instead of the one-direction gain. The function returns what it can contribute to the parent — which can only go one direction. Returning node.val + left_gain + right_gain would let a path branch at every node going upward, which is invalid.

Initializing global_max to 0. If all values are negative, the answer is the largest (least negative) single node, which is negative. Initialize to float('-inf'), not 0.