124. Binary Tree Maximum Path Sum

Edited by Charles

Hard · Python · Binary Search

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given the root of a binary tree, return the maximum path sum of any non-empty path.

A path is a sequence of nodes where each pair of adjacent nodes has an edge connecting them.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem

Given the root of a binary tree, return the maximum path sum of any non-empty path.

A path is a sequence of nodes where each pair of adjacent nodes has an edge connecting them.

A node can appear in the path at most once.

The path does not need to pass through the root.

Example

        -10
        / \
       9   20
          /  \
         15   7

The maximum path is:

15 → 20 → 7

Therefore:

15 + 20 + 7 = 42

Output:

42

The key idea is to distinguish between two different values:

1. The complete path through the current node, which is used to update the global maximum.
2. The one-sided path starting from the current node, which is returned to its parent.

This distinction is necessary because a valid path cannot branch.

Define:

dfs(node)

as:

The maximum path sum starting from node and going downward along only one branch.

Suppose:

        20
       /  \
     15    7

From 20, there are two possible paths that can be returned upward:

20 → 15

or:

20 → 7

We choose the larger one:

20 + max(15, 7)
= 35

Therefore:

return node.val + max(left, right)

Suppose 20 has a parent:

          10
           |
          20
         /  \
       15    7

If 20 returned both sides:

15 → 20 → 7

and then the parent 10 tried to connect to it, we would get:

          10
           |
          20
         /  \
       15    7

This is a Y-shaped structure, not a path.

A valid path cannot branch.

Therefore, when returning information to the parent, the current node can choose only:

node → left

or:

node → right

So:

return node.val + max(left, right)

Although we cannot return both sides to the parent, the current node itself can be the highest point of a complete path.

For example:

        20
       /  \
     15    7

A valid complete path is:

15 → 20 → 7

Therefore, at the current node, we calculate:

node.val + left + right

For this example:

20 + 15 + 7 = 42

This path cannot be extended upward anymore, but it may be the answer to the entire problem.

Therefore, we use it to update the global maximum:

self.res = max(
    self.res,
    node.val + left + right
)

This is the most important distinction in this problem.

Complete Path

Used to update the final answer:

node.val + left + right

Graphically:

        node
       /    \
    left    right

or:

left → node → right

Both sides can be used because the path ends at the current subtree.

Returned Path

Used by the parent:

node.val + max(left, right)

Graphically:

        node
       /
    left

or:

        node
          \
          right

Only one side can be selected because the parent may continue the path upward.

Comparison

Complete path:

left → node → right

node.val + left + right

Used to:
Update global answer

Returned path:

node → left
      OR
node → right

node.val + max(left, right)

Used to:
Return to parent

A simple way to remember:

Update answer → both sides

Return upward → one side

At every node, we need to know:

maximum contribution from left subtree
maximum contribution from right subtree

before we can calculate the answer for the current node.

Therefore, the processing order is:

Left
 ↓
Right
 ↓
Current Node

which is exactly Postorder Traversal.

left = dfs(node.left)
right = dfs(node.right)

# process current node

Suppose:

       5
      /
    -10

If we include the left subtree:

5 + (-10) = -5

But simply taking:

5

is better.

Therefore, if a subtree contributes a negative value, we should ignore it.

We write:

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

This means:

positive contribution → use it

negative contribution → treat it as 0

In other words:

If adding a subtree makes the path worse,
do not include that subtree.

We use:

self.res = float('-inf')

instead of:

self.res = 0

because all node values could be negative.

For example:

    -3

The correct answer is:

-3

If we initialize:

self.res = 0

then the result would incorrectly remain:

0

Therefore:

self.res = float('-inf')

allows negative answers.

Consider:

        -10
        / \
       9   20
          /  \
         15   7

Node 9

Both children are empty:

left = 0
right = 0

Complete path:

9 + 0 + 0 = 9

Update:

res = 9

Return:

9 + max(0, 0) = 9

Node 15

Complete path:

15

Return:

15

Node 7

Complete path:

7

Return:

7

Node 20

Now:

left = 15
right = 7

Complete path:

15 → 20 → 7

Sum:

15 + 20 + 7 = 42

Update:

res = 42

But the value returned to -10 can only use one side:

20 + max(15, 7)
= 35

So:

return 35

Node 10

We receive:

left = 9
right = 35

Complete path through -10:

9 + (-10) + 35
= 34

Compare with the existing answer:

max(42, 34) = 42

Therefore:

Final Answer = 42

For every node:

            node
           /    \
        left    right

          ↓ DFS ↓

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

          ↓

Complete path through node:

left + node.val + right

          ↓

Update global answer:

self.res = max(
    self.res,
    node.val + left + right
)

          ↓

Return a one-sided path:

node.val + max(left, right)

          ↓

        Parent

There are only two formulas that need to be remembered.

Formula 1 — Update Global Answer

self.res = max(
    self.res,
    node.val + left + right
)

Meaning:

left → node → right

Both sides can be included.

Formula 2 — Return to Parent

return node.val + max(left, right)

Meaning:

node → left

or:

node → right

Only one side can be included.

Time Complexity

Each node is visited exactly once:

O(n)

where n is the number of nodes.

Space Complexity

The recursion stack depends on the height of the tree:

O(h)

For a balanced tree:

O(log n)

For a completely skewed tree:

O(n)

The core of LeetCode 124 is understanding that the value used to update the answer and the value returned to the parent are different.

Update global answer:

left + node + right

→ both sides can be used
→ complete path

while:

Return to parent:

node + max(left, right)

→ only one side can be used
→ path must not branch

Remember:

Update answer → both sides

Return upward → one side

That is the key idea behind LeetCode 124.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 9, 2026

Python solution

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.res = float('-inf')

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

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

            self.res = max(
                self.res,
                node.val + left + right
            )

            return node.val + max(left, right)

        dfs(root)

        return self.res

---

Back to Bonus Array · All Algorithm notes