124. Binary Tree Maximum Path Sum

Problem¶

Given a non-empty binary tree, find the maximum sum of any simple path. The path may start and end at any nodes and does not need to include the root.

Tree: [-10, 9, 20, None, None, 15, 7]
Best path: 15 -> 20 -> 7
Output: 42

Key trick¶

For each node, compute the maximum downward gain that can be extended by its parent, while separately updating the answer with a path joining both children through that node.

Trap¶

A path passed to the parent can use only one child, although the completed path may use both.
Negative child gains must be discarded.
Initializing the answer to zero breaks all-negative trees.
Preorder positions do not preserve child indices unless the tree is represented as a complete heap array.
Recursive DFS may exceed Python's recursion limit on a highly skewed tree.

Why is it interesting?¶

It demonstrates tree DP with two related states: an extendable one-branch path and a completed path that may join two branches.

Python solution¶

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        best = root.val
        sums = {None: 0} # child sums: node -> best sum downward
        stack = [(root, False)]

        while stack:
            node, expanded = stack.pop()

            if not expanded:
                # Process both children before computing this node's downward sum
                stack.append((node, True))
                if node.left:
                    stack.append((node.left, False))
                if node.right:
                    stack.append((node.right, False))
                continue


            # Negative branches can only reduce a path's sum.
            left = max(sums[node.left], 0)
            right = max(sums[node.right], 0)

            # A completed path may connect both branches through this node.
            best = max(best, node.val + left + right)

            # A parent can extend only one branch without repeating this node.
            sums[node] = node.val + max(left, right)

            # Child sums are no longer needed.
            if node.left:
                del sums[node.left]
            if node.right:
                del sums[node.right]

        return best

Time complexity: \(O(n)\).

Space complexity: \(O(h)\), where \(h\) is the tree height.

Comment on my solution¶

Your bottom-up DP idea is correct, but converting the tree to preorder values destroys its topology. The formulas 2 * i + 1 and 2 * i + 2 identify children only in a complete heap-style representation, not in a preorder traversal.

For the failing example, preorder produces:

[-10, 9, 20, 15, 7]

The index calculation incorrectly treats 15 and 7 as children of 9, although they are children of 20.

The recurrence also needs to:

Allow the current node without either child.
Ignore negative child gains.
Return only one child branch to the parent.
Use both child branches only when updating the global answer.

# Wrong Answer: 37/97 testcases passed
# [-10,9,20,null,null,15,7]
# output: 34
# expected: 42
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        best = float("-inf")
        preorder = []

        def dfs(node):
            nonlocal best
            if not node:
                return

            # take max value among the leaves as a starting best
            if not node.left and not node.right:
                best = max(best, node.val)

            preorder.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)

        n = len(preorder)
        for i in range(n // 2 - 1, -1, -1):
            l = 2*i + 1
            r = 2*i + 2
            l_val = preorder[l] if l < n else 0
            r_val = preorder[r] if r < n else 0
            left = preorder[i] + l_val
            right = preorder[i] + r_val
            combined = preorder[i] + l_val + r_val

            preorder[i] = max(left, right)
            best = max(best, left, right, combined)

        return best

Extra¶

Differences between @dataclass and regular classes¶

Why using the class defined with @dataclass is not hashable and the other is?

When is better to define a class in one way over the other?

Isn't it better anyway to use id(...) instead of the instance? I mean in term of memory usage?

Should I update my library to define classes without @dataclass?

Why is the dataclass unhashable?¶

By default, @dataclass generates value-based __eq__. Because its fields are mutable, Python disables __hash__ to prevent dictionary keys from changing after insertion.

A regular class inherits identity-based equality and hashing from object, so distinct instances remain hashable regardless of their fields.

When should each style be used?¶

Use @dataclass for value-like objects where equality should compare fields.
Use @dataclass(frozen=True) for immutable, hashable values.
Use a regular class for mutable nodes whose identity matters.
Use @dataclass(eq=False) when you want dataclass conveniences but identity-based equality and hashing.

For tree and graph nodes, identity usually matters more than structural equality.

Is using `id(...)` better for memory?¶

Usually not.

An instance used as a dictionary key stores only a reference to the existing object.
id(node) produces an integer key, which must also be stored and may require a separate integer object.
Object keys are clearer and avoid concerns about ID reuse after an object is destroyed.

Prefer instances as keys when they have identity-based hashing. Use id(...) only when the class cannot be changed or made hashable.

Should the library remove `@dataclass`?¶

You can keep it, but disable generated equality:

@dataclass(eq=False)
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None
    next: Optional["TreeNode"] = None

This provides concise initialization and representation while restoring identity-based equality and hashing. It is a good default for mutable linked-list, tree, and graph nodes.

Example¶

from dataclasses import dataclass


# Regular class: identity-based equality and hashing.
class RegularNode:
    def __init__(self, value):
        self.value = value


a = RegularNode(1)
b = RegularNode(1)

print(a == b)             # False: different objects
print(len({a, b}))        # 2: both are valid set keys


# Mutable dataclass: value-based equality, but no hashing.
@dataclass
class MutablePoint:
    x: int
    y: int


p1 = MutablePoint(1, 2)
p2 = MutablePoint(1, 2)

print(p1 == p2)           # True: fields are equal

try:
    {p1}
except TypeError as error:
    print(type(error).__name__)  # TypeError

# Hashing would be unsafe because equality can change after mutation.
p1.x = 99
print(p1 == p2)           # False


# Frozen dataclass: immutable, value-based, and hashable.
@dataclass(frozen=True)
class FrozenPoint:
    x: int
    y: int


f1 = FrozenPoint(1, 2)
f2 = FrozenPoint(1, 2)

print(f1 == f2)           # True
print(len({f1, f2}))      # 1: equal values are the same set key


# Dataclass node: mutable but identity-based.
@dataclass(eq=False)
class TreeNode:
    value: int
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


n1 = TreeNode(1)
n2 = TreeNode(1)

print(n1 == n2)           # False: different objects
print(len({n1, n2}))      # 2: both are valid set keys