Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

What is this problem about?

Binary Tree Maximum Path Sum is a classic "Hard" coding problem. A "path" is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Your task is to find the maximum possible sum of values along such a path. Since node values can be negative, this is much trickier than a simple tree traversal.

Why is this asked in interviews?

This is a favorite for top-tier companies like Meta, Amazon, and Google. It tests your mastery of recursion and your ability to handle "negative gain." It forces you to distinguish between two different things: the maximum path that can be extended to a parent, and the maximum path that exists within a subtree (which might not include the parent).

Algorithmic pattern used

This problem uses the Post-order Traversal (DFS) combined with Dynamic Programming on trees. At each node, you calculate the "maximum contribution" it can offer to its parent. This contribution is node.val + max(0, left_gain, right_gain). Simultaneously, you update a global maximum by considering a path that "turns" at the current node: node.val + left_gain + right_gain.

Example explanation

Consider this tree: -10 /
9 20 /
15 7

1. For node 15: Max gain is 15.
2. For node 7: Max gain is 7.
3. For node 20:
   • It can form a path through itself: 15 + 20 + 7 = 42. (Update global max to 42).
   • It returns to its parent (-10) its best "one-way" path: 20 + max(15, 7) = 35.
4. For node -10:
   • Path through -10: 9 + (-10) + 35 = 34.
   • Global max stays 42.

Common mistakes candidates make

The biggest mistake is not handling negative values correctly. If a subtree has a negative maximum gain, it’s better to ignore it (treat it as 0) rather than adding it to the current path. Another mistake is trying to return the "split" path sum (left + root + right) to the parent, which is illegal as a path cannot branch into two children.

Interview preparation tip

This problem is the "ultimate" tree recursion test. If you can explain why you return max(left, right) + node.val but update the global max with left + right + node.val, you've demonstrated a deep understanding of tree-based algorithms.