# LeetCode 124: Binary Tree Maximum Path Sum — Step-by-Step Visual Trace

**Hard** — Binary Tree | Depth-First Search | Recursion | Dynamic Programming

## The Problem

Find the maximum sum of any path in a binary tree, where a path is defined as any sequence of nodes connected by parent-child relationships. The path can start and end at any nodes in the tree.

## Approach

Use recursive depth-first search to calculate the maximum path sum ending at each node. At each node, consider the maximum contribution from left and right subtrees (ignoring negative contributions), update the global maximum with the path passing through the current node, and return the maximum single-branch path sum.

**Time:** O(n) · **Space:** O(h)

## Code

```python
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def maxPathSumHelper(node):
            if not node:
                return 0

            left_sum = max(0, maxPathSumHelper(node.left))
            right_sum = max(0, maxPathSumHelper(node.right))

            self.max_sum = max(self.max_sum, left_sum + right_sum + node.val)

            return max(left_sum, right_sum) + node.val

        self.max_sum = float("-inf")
        maxPathSumHelper(root)

        return self.max_sum
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0124_binary-tree-maximum-path-sum)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0124_binary-tree-maximum-path-sum) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*