Binary Tree Maximum Path Sum

This is the hard problem that closes the section, and it is really Diameter of Binary Tree with values. The same split applies — return what the parent can extend, record what it cannot — with two extra decisions: a branch whose sum is negative should be left out, and the path must contain at least one node even when every value is negative.

It is asked often at large companies precisely because it looks intimidating and collapses to about ten lines once you see the structure. If you have understood the diameter lesson, the only new ideas here are the clamp and the starting value.

The problem

Given the root of a binary tree whose nodes hold integers (possibly negative), return the largest possible sum of a path. A path is a sequence of nodes where each pair of neighbours is joined by an edge, no node appears twice, and there is at least one node. It does not have to pass through the root, and it does not have to reach a leaf.

          -20        /     \       6       5      / \     / \     3  -1   4   7

• For this tree the answer is 16: the path 4 – 5 – 7. The best path through the root, 3 – 6 – (−20) – 5 – 7, sums to only 1.
• For a single node with value −3, the answer is -3: the path must contain at least one node.

Constraints: 1 ≤ n ≤ 3 × 10⁴ nodes, values between −1000 and 1000.

Clarifying questions

• Must the path go through the root, or reach a leaf? Neither.
• Can the path be empty (sum 0)? No — at least one node. This decides the starting value of the best.
• Can it go up and then down? Yes, once: up to a highest node, then down the other side. It cannot visit a node twice.
• Return the sum or the path? The sum.

Approach 1: the simple way

Every path has one highest node, its "peak". The best path peaking at a node is: the node's value, plus the best downward path from its left child (if positive), plus the best downward path from its right child (if positive). So try every node as the peak, and compute the best downward paths from scratch each time.

1def best_down(node: Optional[TreeNode]) -> int:2    """Best sum of a path that starts at node and goes down (0 if empty)."""3    if node is None:4        return 05    return node.val + max(0, best_down(node.left), best_down(node.right))678def max_path_sum_brute(root: TreeNode) -> int:9    """Try every node as the top of the path; recompute downward gains each time."""10    best = float("-inf")11    stack = [root]12    while stack:13        node = stack.pop()14        through = node.val + max(0, best_down(node.left)) + max(0, best_down(node.right))15        best = max(best, through)16        for child in (node.left, node.right):17            if child:18                stack.append(child)19    return best

Correct, and the idea is exactly right. But best_down walks a whole subtree, and it is called at every node, so every node is re-walked once per ancestor: O(n × h). On a chain of 3 × 10⁴ nodes that is about 4.5 × 10⁸ steps, plus recursion 3 × 10⁴ deep. (Checking every pair of nodes and summing the path between them is worse still: O(n²) pairs, each path up to O(n) long.)

The key insight

best_down for every node can be computed in one postorder pass: a node's best downward path is its value plus the better of its children's, if that is positive. And at the moment a node has both children's values in hand, it can also compute the best path peaking at itself. The same two outputs as in the diameter lesson, going to different places:

• Return the gain — node.val + max(left, right). A parent can extend a path that goes down one side of this node.
• Record the peak — node.val + left + right. A path that uses both sides is closed; no parent can extend it.

Two more rules make it correct with negative values:

• Clamp each child's gain at 0. A negative gain would only lower any path that uses it, so it is better to stop at this node: left = max(gain(node.left), 0). Taking 0 means "do not go down that side".
• Start best at negative infinity, not 0. Starting at 0 means "the empty path", which is not allowed. On an all-negative tree the answer must be the largest single value, and only −∞ lets that through.

Approach 2: one pass, return the gain, record the peak

1def max_path_sum(root: TreeNode) -> int:2    """Largest sum of any path (at least one node) in the tree."""3    best = float("-inf")45    def gain(node: Optional[TreeNode]) -> int:6        nonlocal best7        if node is None:8            return 09        left = max(gain(node.left), 0)    # a negative branch is better left out10        right = max(gain(node.right), 0)11        best = max(best, node.val + left + right)   # path that peaks at this node12        return node.val + max(left, right)          # one side only: the parent extends it1314    gain(root)15    return best

The base case returns 0 for a missing child: "nothing to add". That is safe because the clamp would turn any negative into 0 anyway, and the node's own value is always included in the peak.

Dry run on the example tree

Calls finish in postorder: 3, −1, 6, 4, 7, 5, −20.

Three moments matter. At node 6, the right child's gain of −1 is clamped to 0, so the best path through 6 is 3 – 6 = 9 and skips −1. At node 5, the peak 4 + 5 + 7 = 16 is recorded — but only 5 + 7 = 12 is returned, because a parent can use one side only. At the root, the peak is −20 + 9 + 12 = 1, far below 16. The answer 16 was recorded two levels down and never returned.

Complexity. Time is O(n): each node is visited once with O(1) work. Space is O(h) for the recursion — O(log n) balanced, O(n) for a chain. For very deep trees, compute the same gains in an iterative postorder with a dictionary.

Edge cases

• All values negative. [-1, -2, -3] (root −1 with children −2 and −3) → −1. Both children's gains clamp to 0, the root's peak is −1, and only a best that starts at −∞ can hold it.
• A single node. Its peak is its own value; the answer is that value, even if negative.
• The answer does not reach a leaf. In [2, -1] (root 2 with left child −1) the answer is 2: the clamp stops the path at the root.
• The answer is deep in a subtree. The lesson's example: the recorded best comes from node 5, not the root.

Saying it in the interview

Follow-ups

• "The path must start at the root and go down." Nothing needs recording on the side: the answer is gain(root) itself — the root's value plus the better clamped child gain, stopping wherever the sum stops improving.
• "The path must go from a leaf to a leaf." Only record a peak at nodes with two children, and do not clamp — a leaf-to-leaf path must go all the way down both sides.
• "Return the path, not the sum." Also return which child gave the gain, and remember the peak node and its two arms when best improves; then walk down the arms to list the nodes.