DSA With AI
Week 4 ยท Trees

Binary Tree Maximum Path Sum

Find the maximum sum over any non-empty path in a binary tree. A path can start and end at any nodes, but it cannot branch more than once through a node.

Hard Trees Week 4 Practice runner

Frame the problem

  • Node values can be negative.
  • The path does not need to include the root.
  • A path may use both children only at its highest turning node.
1. Reveal example inputs and outputs

Example 1

Input:

max_path_sum([
  1,
  [
    2,
    null,
    null
  ],
  [
    3,
    null,
    null
  ]
])

Output:

6

Example 2

Input:

max_path_sum([
  -10,
  [
    9,
    null,
    null
  ],
  [
    20,
    [
      15,
      null,
      null
    ],
    [
      7,
      null,
      null
    ]
  ]
])

Output:

42
2. Brute force first

For each node, what would you need to know about the best downward path from each child?

3. Reveal the insight ladder
  1. A parent can only extend one child path upward.
  2. A complete answer at a node may use left gain + node + right gain.
  3. Negative child gains should be dropped because they reduce the sum.
  4. Maintain a global best for complete paths while returning only one-side gains to the parent.
4. Dry run before code
  1. Tree [-10, 9, 20, 15, 7].
  2. Leaf gains are 9, 15, and 7.
  3. At 20, the complete path is 15 + 20 + 7 = 42.
  4. The gain returned to -10 is 20 + max(15, 7) = 35, but the global best remains 42.
5. Reveal final Python solution 
def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        value, left, right = node
        left_gain = max(gain(left), 0)
        right_gain = max(gain(right), 0)
        best = max(best, value + left_gain + right_gain)
        return value + max(left_gain, right_gain)

    gain(root)
    return best

Complexity: Time O(n), space O(h) for recursion.

Interview narration

  • I will distinguish the value returned upward from the global best path.
  • The return value must be a single chain because a parent cannot accept a forked path.
  • The global update can use both children because the current node can be the path's turning point.

Common traps

  • Returning a forked path to the parent.
  • Initializing best to 0 and failing all-negative trees.
  • Forgetting to drop negative child gains.

Follow-up drills

1. Why can the returned gain use only one child?

A returned path must remain extendable by the parent. If it used both children, adding the parent would create a branching path, which is invalid.

2. What changes if the problem asks for root-to-leaf maximum path sum?

You cannot drop a required child just because it is negative; the path must continue to a leaf. The recurrence and base cases change.

3. How would you return the actual path too?

Track the best path nodes alongside each downward gain. On each global update, combine the left downward path, current node, and right downward path.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.