A billing product stores a contribution tree: each SKU forks into at most two child SKUs. The SLO for a catalog review is the highest-sum path of any connected SKUs — a node can be a loss, a lone SKU can win, and the path does not have to pass through the root. The intern version, at every SKU, walked the left fork for max downward gain, walked the right fork for max downward gain, added them to the node, then did the same work in both children. A dozen SKUs painted instantly. A million-node imported catalog still re-walked the same leaves from every ancestor.

The value you return to the parent is node + max(0, leftGain, rightGain) — one child, because a path to the parent cannot fork. The path through the node, the one that updates the global max, is node + max(0, leftGain) + max(0, rightGain) — both children, negatives dropped. Diameter is the same post-order shape; it counts edges, this sums values. A binary tree already gives left and right. DFS owns recursion versus an explicit stack. Here we only care about a one-child gain out and a running max of the through-path. Do not stamp finish times or hunt back edges.

The problem

Given the root of a binary tree, return the maximum path sum of any non-empty path. A path is any sequence of nodes with an edge between neighbors; a node appears at most once. The path does not have to pass through the root. Node values can be negative. A single node can be the answer.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees, summing values not counting edges:

      1
     / \
    2   3       →  6

      1
     / \
   -2   3       →  4   (drop -2)

     -10
     /  \
    9   20
       /  \
     15    7    →  42

    -3          →  -3
[]              →  this prompt usually has at least one node

Note: This prompt’s constraints start at one node. If an interviewer hands you null, say so — returning Integer.MIN_VALUE is not an empty-tree answer. Do not initialize the running max to 0; an all-negative tree would then lose to a fake empty path.

Gain from scratch at every node is the honest brute force

At each node, compute max downward gain of the left subtree and of the right, clamp negatives, add them to the node as the path through this node, then take the max with the same work in both children. Correct. Extra: every ancestor re-walks the same descendants. Collecting every pair of nodes is the same answer with more furniture — the best path through a node is already the best one-child gain on each side.

The Java is that nested walk:

int maxPathSumCollect(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    everyNode(root, best);
    return best[0];
}

void everyNode(TreeNode node, int[] best) {
    if (node == null) {
        return;
    }
    int through = node.val
            + Math.max(0, maxDown(node.left))
            + Math.max(0, maxDown(node.right));
    best[0] = Math.max(best[0], through);
    everyNode(node.left, best);
    everyNode(node.right, best);
}

int maxDown(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return node.val
            + Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)));
}

At a dozen nodes this is a rounding error. At a million-node spine you still walk overlapping subtrees from every ancestor. The intended answer never asks gain twice: one DFS returns a one-child gain and updates a running max of node + both children.

One DFS, one child out, both children on the side

Null returns 0. A node asks both children for gain, clamps each with max(0, …) so a negative child is dropped instead of taken, offers node.val + left + right to the global max, and returns node.val + max(left, right) — one child, because the path that continues to the parent cannot fork. Initialize that global max to Integer.MIN_VALUE (or the first node’s value) because all-negative trees exist.

Walk the tree with a negative child:

      1
     / \
   -2   3

gain(-2) = -2,  through = -2
gain(3)  =  3,  through =  3
at 1:
  left  = max(0, -2) = 0     drop the negative child
  right = max(0,  3) = 3
  through = 1 + 0 + 3 = 4    both children, after the clamp
  return  1 + max(0, 3) = 4  one child up
best = max(-2, 3, 4) = 4

The Java is that recurrence with a one-slot box for the max:

int maxPathSum(TreeNode root) {
    int[] best = {Integer.MIN_VALUE};
    gain(root, best);
    return best[0];
}

int gain(TreeNode node, int[] best) {
    if (node == null) {
        return 0;
    }
    int left = Math.max(0, gain(node.left, best));
    int right = Math.max(0, gain(node.right, best));
    best[0] = Math.max(best[0], node.val + left + right);
    return node.val + Math.max(left, right);
}

Time is O(n) — each node is visited once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

What interviewers usually poke next

  • One child vs both. The return is one child because a path to the parent cannot fork. The through-path is both. Returning node + left + right to the parent double-counts a fork the ancestor cannot use.
  • Edges vs sums. Diameter uses the same post-order shape and counts edges (leftHeight + rightHeight). This sums values and a node may start a new path. Do not drop node.val the way diameter drops a + 1 into height-only returns.
  • All-negative trees. A single node can be the answer. Seed best with Integer.MIN_VALUE or the first node, never 0.
  • Empty tree. Constraints here start at one node. If root == null is in play, agree on 0 or an exception — do not ship MIN_VALUE.
  • Million-node spine. Recursion depth is O(h). Say you would switch to an explicit stack so the JVM does not blow the stack.

You are done with this problem when you can say a single node can win, a negative child is dropped not taken, the parent sees one child, and the global max sees both — not nested gain walks from every ancestor.