DSA sheet · Trees · DFS pattern

Binary Tree Maximum Path Sum

LeetCode marks this one Hard, but the teacher's view is that it isn't, once you've done Diameter of Binary Tree. It's the same shape of DFS: each node writes "best path that bends at me" on a board, and returns only its best single branch to its parent. The new part is negative numbers. She builds the solution in two steps on purpose: first a version that thinks only about positive values (it passes the sample tests), then she changes one value to a negative number, shows the code giving a wrong answer, and fixes it with two small max(0, …) changes. We follow the same two steps.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Words you must know first
• Part A · First version (thinking only of positive values)
• Part B · The fix for negative values (final answer)
• Part C · Revision page

Part 0 · Words you must know first

Part A · First version (positive thinking)

LeetCode 124

1The question in simple words

Given the root of a binary tree, return the largest path sum over all possible paths. The path can start and end at any nodes. It doesn't need to touch the root, and it doesn't need to reach a leaf.

        -10
        /  \
       9    20
           /  \
          15    7

Some paths: 7 alone (sum 7), 20 – 7 (27), 15 – 20 – 7 (42), 9 – (−10) – 20 – 15 (34). The best is 42: it bends at 20 and skips the root, because the root is negative.

2What the constraints tell us

• Nodes: 1 to 3 × 10⁴. At least one node, so an answer always exists. An O(n) solution (visit each node once) is about 3 × 10⁴ steps, far below the danger line of about 10⁸, so it's completely safe.
• Values: −1000 to 1000. Two things come from this.
  • Negatives exist → we'll need to be careful when choosing what to add (Part B).
  • int or long? We are adding values, so check the biggest possible sum. The worst tree for this is shaped like a "V": a long chain going left and a long chain going right from the root. Then one path can contain almost all 3 × 10⁴ nodes. If each is 1000, the sum is 1000 × 3 × 10⁴ = 3 × 10⁷ (adding 1000 that many times is the same as multiplying). An int holds about 2 × 10⁹, so a normal int is enough. (Python ints never overflow, but this check matters in Java/C++.)

3Intuition

Why DFS? A path is a chain of connected nodes. BFS jumps across a whole level, mixing nodes that aren't joined. DFS naturally walks along parent → child chains, so it fits a path question much better.

The picture: every path has one highest node, the place where it bends. If we stand on a node and pretend all values are positive, the best path bending here is:

Try every node as the bending point, keep the largest. Exactly like Diameter, but adding values instead of counting edges.

4Building the logic from examples

Base case

Leaves like 9 have no children. The parent wants to add what the children give back, so an empty child returns 0 (adds nothing).

The board: max_sum, and why it starts at minus infinity

We keep the best path sum seen so far in a variable outside the recursion. Since values can be negative, the best answer itself can be negative (a tree that is just [-3] has answer −3). If we started at 0, we'd wrongly answer 0. The teacher's general rule:

At each node, after getting left and right from the children: max_sum = max(max_sum, node.val + left + right).

What should a node return? The teacher tries three ideas

Idea 1: return max_sum? Watch leaves 15 and 7 under node 20. After 15 is done, the board says 15. If 7 returned the board, it would hand 15 to node 20, but 7's side is really worth only 7. Wrong.

Idea 2: return just node.val? For the leaves that's right (15 and 7 return themselves). But now imagine the root were +10 instead of −10. The best path would be 9 + 10 + 20 + 15 = 54. For node 10 to find it, node 20 must hand up 20 + 15 = 35. Returning only 20 gives 9 + 10 + 20 = 39. Too small.

Idea 3: return node.val + max(left, right). The parent can only continue the path into one of 20's sides, either 20 → 15 or 20 → 7. Both include 20 itself, so the return is 20 plus the better side: 20 + 15 = 35. Right.

5Approach steps

1. Set max_sum = −∞. Run dfs(root). Return max_sum.
2. In dfs(node): None → return 0.
3. left = dfs(node.left), right = dfs(node.right).
4. max_sum = max(max_sum, node.val + left + right).
5. Return node.val + max(left, right).

6Code (Python), first version

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')       # looking for a max: start at -infinity
        self.dfs(root)
        return self.max_sum

    def dfs(self, root):
        if root is None:
            return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        self.max_sum = max(self.max_sum, root.val + left + right)   # bend here
        return root.val + max(left, right)                          # one branch up

7Code line by line

8Dry run

1. dfs(−10) → dfs(9): both children None → 0, 0. Board: max(−∞, 9) = 9. Returns 9 + 0 = 9.
2. dfs(−10) goes right → dfs(20) → dfs(15): 0, 0 → board max(9, 15) = 15. Returns 15.
3. dfs(7): 0, 0 → 7 < 15, board stays 15. Returns 7.
4. dfs(20): left 15, right 7 → 20 + 15 + 7 = 42 → board 42. Returns 20 + max(15, 7) = 35.
5. dfs(−10): left 9, right 35 → −10 + 9 + 35 = 34 < 42, board stays 42. Returns 25 (not needed).
6. Answer: 42 ✓ (LeetCode's samples pass with this version.)

9Complexity & remember

• Time O(n): each node is visited once.
• Space O(n): the call stack, as tall as the tree (n in the worst, line-shaped case).

Part B · The fix for negative values

1The question, with a twist

Same question. The teacher changes one value to break the Part A code: 15 becomes −15.

        -10
        /  \
       9    20
           /  \
        -15    7

Now the best path is just 20 – 7 = 27. We should not take −15 at all: a path may stop wherever it likes, so we can simply leave the bad part out.

2Constraints

Same as Part A. The only one that matters now is "values can be negative".

3Intuition

A child's branch is an offer: "you can add me to your path." If the offer is negative, adding it makes the path worse. So we should refuse negative offers and add 0 instead, meaning "the path stops at this node on that side".

First, watch the Part A code fail

1. dfs(9) → board 9, returns 9.
2. dfs(−15): −15 + 0 + 0 = −15 < 9, board stays 9. Returns −15.
3. dfs(7): board stays 9. Returns 7.
4. dfs(20): 20 + (−15) + 7 = 12 → board 12. It was forced to include −15. Returns 20 + max(−15, 7) = 27.
5. dfs(−10): −10 + 9 + 27 = 26 → board 26.
6. Output 26 ✗, but the expected answer is 27. The code took the path 9 – (−10) – 20 – 7 and never tried 20 – 7 on its own, because at node 20 it always added the −15.

4Building the fix

You could write an if/else: "if left is negative, use 0". The short way says the same thing in one line:

left = max(0, self.dfs(root.left))     # negative offer -> take 0
right = max(0, self.dfs(root.right))

If the child's branch is negative, max picks 0. If it's positive, max keeps it. Nothing else in the code changes.

5Approach steps (the new step is 3)

1. Board = −∞. Run dfs(root). Return the board.
2. None → 0.
3. left = max(0, dfs(left child)), right = max(0, dfs(right child)).
4. Board = max(board, val + left + right).
5. Return val + max(left, right).

6Code (Python), final

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')
        self.dfs(root)
        return self.max_sum

    def dfs(self, root):
        if root is None:
            return 0
        left = max(0, self.dfs(root.left))     # drop a negative left branch
        right = max(0, self.dfs(root.right))   # drop a negative right branch
        self.max_sum = max(self.max_sum, root.val + left + right)
        return root.val + max(left, right)

7Code line by line (what changed)

8Dry run on the −15 tree

1. dfs(9): left 0, right 0 → board 9. Returns 9.
2. dfs(−15): −15 + 0 + 0 = −15, board stays 9. Returns −15.
3. dfs(7): board stays 9. Returns 7.
4. dfs(20): left = max(0, −15) = 0, right = max(0, 7) = 7. Board: 20 + 0 + 7 = 27. Returns 20 + 7 = 27.
5. dfs(−10): left = max(0, 9) = 9, right = max(0, 27) = 27. −10 + 9 + 27 = 26 < 27, board stays 27.
6. Answer: 27 ✓ (path 20 – 7)

On the original tree (15 positive) nothing is ever clamped except empty children, so the answer is still 42.

9Complexity & remember

• Time O(n), space O(n) for the call stack. Same as Part A: two max calls cost nothing extra.

Part C · Revision page

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

s = Solution()
print(s.maxPathSum(TreeNode(1, TreeNode(2), TreeNode(3))))                                # 6
print(s.maxPathSum(TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))  # 42
print(s.maxPathSum(TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(-15), TreeNode(7))))) # 27
print(s.maxPathSum(TreeNode(-3)))                                                         # -3
print(s.maxPathSum(TreeNode(-2, TreeNode(-1))))                                           # -1

Based on this video: Binary Tree Maximum Path Sum