Tree Path Sum and Maximum Path

Binary Tree Maximum Path Sum

LeetCode 124 gives you a binary tree and asks you to find the path with the largest sum. The path can start and end at any node in the tree: it does not need to pass through the root, and it does not need to end at a leaf. A path is any sequence of nodes where each pair of adjacent nodes is connected by an edge, and no node appears more than once.

This is one of the trickiest tree problems because the "best" path could be hiding anywhere. It might be a single node deep in the tree. It might run from one leaf up through some ancestor and back down to another leaf. It might be a straight downward chain. The path is not constrained to any particular structure, so we need a strategy that considers every possibility without blowing up the runtime.

Why This Is Hard

In simpler path-sum problems, you walk from the root to a leaf, accumulating a sum along the way. The direction is always downward, and the starting point is always the root. Here, the path can bend. It can go down from some node, come back up through that node, and then go down the other side. This "arch" shape is what makes the problem interesting.

The challenge is that a recursive function can only return one value to its parent. When we are standing at a node and want to tell our parent about the best path through us, we have to pick one direction (left or right) because the parent will extend the path further upward. We cannot tell the parent "I go both left and right" because that would create a path that branches, which is not allowed.

But we still need to consider the arch. The trick is to separate what we evaluate from what we return.

The Key Insight: Evaluate the Arch, Return One Direction

At each node, we compute two things:

The "arch" value is the best path that passes through this node and potentially uses both children. This is node.val + left_gain + right_gain, where left_gain is the best sum we can get going down the left subtree, and right_gain is the best sum going down the right subtree. This arch value is a candidate for the global answer, so we compare it against our running maximum.

The "return" value is the best downward extension from this node in one direction only. This is node.val + max(left_gain, right_gain). We return this to the parent so it can build a longer path.

This separation is the heart of the algorithm. We update the global answer with the arch (both children), but we return to the parent with a single-direction extension (one child).

Clamping Negative Contributions

What if the left subtree contributes a negative sum? Including it would make our path worse, so we should just skip it. We handle this by clamping each child's contribution to zero:

left_gain = max(dfs(node.left), 0)

If the best path down the left subtree has a negative sum, we treat it as 0, meaning we simply do not extend in that direction. This is equivalent to saying "the path does not enter this subtree at all."

Worked Example

Consider this tree:

-10 / \ 9 20 / \ 15 7

The nodes are [-10, 9, 20, null, null, 15, 7].

Let us trace the DFS. We visit nodes in post-order (left, right, then process).

At node 9 (a leaf): left_gain = 0, right_gain = 0. Arch = 9 + 0 + 0 = 9. Update global answer to 9. Return 9.

At node 15 (a leaf): left_gain = 0, right_gain = 0. Arch = 15. Update global answer to 15. Return 15.

At node 7 (a leaf): left_gain = 0, right_gain = 0. Arch = 7. Global answer stays 15. Return 7.

At node 20: left_gain = 15, right_gain = 7. Arch = 20 + 15 + 7 = 42. Update global answer to 42. Return 20 + max(15, 7) = 35.

At node -10 (root): left_gain = max(9, 0) = 9, right_gain = max(35, 0) = 35. Arch = -10 + 9 + 35 = 34. Global answer stays 42. Return -10 + max(9, 35) = 25.

The answer is 42, which corresponds to the path 15 -> 20 -> 7. Notice that this path does not go through the root at all.

Code: Binary Tree Maximum Path Sum

def max_path_sum(root):
    ans = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)
        # Evaluate the arch through this node
        ans[0] = max(ans[0], node.val + left_gain + right_gain)
        # Return the best single-direction extension
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return ans[0]

We use a list ans = [float('-inf')] rather than a plain variable because Python closures cannot reassign variables in an enclosing scope without the nonlocal keyword. Using a list sidesteps that. Alternatively, you could declare nonlocal ans inside the nested function.

Tree Diameter: Same Pattern, Counting Edges

LeetCode 543 demonstrates this: the diameter of a binary tree is the length of the longest path between any two nodes, measured in edges. This is the exact same arch-vs-return pattern, just counting edges instead of summing values.

At each node, the longest path through it uses the deepest descent into the left subtree plus the deepest descent into the right subtree. That gives the "arch" length in edges. We return the depth of the deeper child plus one (for the edge connecting this node to its parent).

Consider a balanced tree of height 3. The diameter goes from one leaf up to the root and back down to another leaf, giving a path of 6 edges. A skewed tree of 5 nodes has diameter 4.

The only difference from maximum path sum is that we are computing depths instead of sums, and we do not clamp to zero (depths are never negative).

Code: Diameter of Binary Tree

def diameter_of_binary_tree(root):
    ans = [0]

    def depth(node):
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        # Arch: longest path through this node
        ans[0] = max(ans[0], left + right)
        # Return: depth of this subtree
        return 1 + max(left, right)

    depth(root)
    return ans[0]

Notice how similar this is to maximum path sum. The arch updates the global answer with left + right (the number of edges from the deepest left descendant through this node to the deepest right descendant). The return value is 1 + max(left, right), telling the parent the depth of this subtree.

Path Sum: The Simpler Root-to-Leaf Variant

The classic Path Sum problem, LeetCode 112, asks whether there exists a root-to-leaf path whose node values add up to a given target. This is simpler because the path is constrained: it must start at the root and end at a leaf, and it always goes downward.

The approach is to pass the remaining sum downward. At the root, the remaining sum is the target. At each step, subtract the current node's value. When you reach a leaf, check if the remaining sum is exactly zero.

For example, in the tree [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1] with target 22, the path 5 -> 4 -> 11 -> 2 sums to 22. At the root, remaining = 22. After node 5, remaining = 17. After node 4, remaining = 13. After node 11, remaining = 2. At leaf 2, remaining = 0. Found it.

Code: Path Sum (Root-to-Leaf)

def has_path_sum(root, target_sum):
    if not root:
        return False
    target_sum -= root.val
    # If it is a leaf, check if we have reached the target
    if not root.left and not root.right:
        return target_sum == 0
    return (has_path_sum(root.left, target_sum) or
            has_path_sum(root.right, target_sum))

This is a clean top-down recursion. We subtract the current node's value and recurse. The base case checks whether we are at a leaf with exactly zero remaining. There is no need for a global variable here because the answer flows naturally through the return values.

Longest Univalue Path

LeetCode 687 asks you to find the longest path in the tree where every node has the same value, measured in edges. This is another application of the arch-vs-return pattern, but with a twist: we only extend a path through a child if that child's value matches the current node's value.

At each node, we compute how far we can extend downward through the left child (if it matches) and through the right child (if it matches). The arch through this node uses both extensions, and the return value uses only the longer one.

If a child's value does not match, its contribution is zero, because the univalue path cannot continue through a mismatched node.

Code: Longest Univalue Path

def longest_univalue_path(root):
    ans = [0]

    def dfs(node):
        if not node:
            return 0
        left_len = dfs(node.left)
        right_len = dfs(node.right)
        # Extend left only if child matches
        left_arrow = left_len + 1 if node.left and node.left.val == node.val else 0
        # Extend right only if child matches
        right_arrow = right_len + 1 if node.right and node.right.val == node.val else 0
        # Arch through this node
        ans[0] = max(ans[0], left_arrow + right_arrow)
        # Return single-direction extension
        return max(left_arrow, right_arrow)

    dfs(root)
    return ans[0]

The structure is identical to diameter: compute two directional extensions, update the global answer with their sum, and return the longer one. The only added logic is the conditional check on matching values.

Complexity Analysis

All four problems visit every node exactly once, so the time complexity is $O(n)$ where n is the number of nodes.

The space complexity is $O(h)$ where h is the height of the tree, due to the recursion stack. In the worst case (a completely skewed tree), h = n and the space is $O(n)$. For a balanced tree, $h = \log n$.

The arch-vs-return pattern is one of the most important tree techniques to internalize. Once you see that the global answer considers both children while the recursive return value considers only one, you can apply it to maximum path sum, diameter, longest univalue path, and many other variations. The pattern always involves a single DFS with a global variable that captures the best "arch" seen so far, while the return value propagates the best single-direction extension upward to the parent.

Recognizing this pattern

You're probably looking at the arch-vs-return tree pattern when:

• The answer is the best path through some node where the path can bend, going down into the left subtree, through the node, and back down into the right subtree.
• The locally optimal "best path through this node" equals left_arch + node_contribution + right_arch, with each arch clamped at max(arch, 0) to drop negative extensions.
• The recursive return value differs from the global answer: children pass up a single-direction extension, but the global update considers both children.
• Variations include longest path by edge count, longest same-value path, or maximum sum path.

Common templates:

• Max path sum with negative pruning: return node.val + max(0, max(left, right)). Example: Binary Tree Maximum Path Sum.
• Diameter by edge count: return 1 + max(left, right), update global with left + right. Example: Diameter of Binary Tree.
• Univalue path: only count children whose value matches the current node. Example: Longest Univalue Path.
• Root-to-leaf path tally: accumulate state downward and collect at leaves. Example: Path Sum II.