#124 Binary Tree Maximum Path Sum

frequently reported atAdobe Amazon ByteDance / TikTok Salesforce Meta Microsoft

the problem

In plain words

A path is a sequence of nodes connected by edges, each node used at most once; it doesn't need to pass the root. Return the maximum sum of node values on any non-empty path.

in root = [1,2,3]

out 6

2 → 1 → 3.

in root = [-10,9,20,null,null,15,7]

out 42

15 → 20 → 7.

1 ≤ number of nodes ≤ 3·10⁴
-1000 ≤ Node.val ≤ 1000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (bottom-up)Kadane / running best

Same shape as Diameter: return the best one-sided downward path (the parent can only extend one side), record the best two-sided bend. Drop any side whose gain is negative.

solutions

From brute force to optimal

For each node, compute the best downward path from each child with a fresh DFS, and try node + both gains.

down(n) = n.val + max(0, down(left), down(right)).
For every node: node.val + max(0, down(left)) + max(0, down(right)).

timeO(n²) worst

down() re-walks whole subtrees for every node (a skewed tree costs n + (n−1) + …).

spaceO(h)

Recursion and the explicit stack.

javajava.util.*

1class Solution {2    public int maxPathSum(TreeNode root) {3        int best = Integer.MIN_VALUE;4        Deque<TreeNode> stack = new ArrayDeque<>();5        stack.push(root);6        while (!stack.isEmpty()) {                     // try every node as the path's top7            TreeNode node = stack.pop();8            int peak = node.val + Math.max(0, down(node.left)) + Math.max(0, down(node.right));9            best = Math.max(best, peak);10            if (node.left != null) stack.push(node.left);11            if (node.right != null) stack.push(node.right);12        }13        return best;14    }15 16    /** Best sum of a path that starts at node and only goes downwards (fresh walk every call). */17    private int down(TreeNode node) {18        if (node == null) return 0;19        return node.val + Math.max(0, Math.max(down(node.left), down(node.right)));20    }21}

gain(node) returns node.val + the better non-negative child gain, and records node.val + both gains.

best = Integer.MIN_VALUE.
left = max(0, gain(left)), right = max(0, gain(right)).
best = max(best, node.val + left + right).
Return node.val + max(left, right).

timeO(n)

Each node visited once.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    private int best;3 4    public int maxPathSum(TreeNode root) {5        best = Integer.MIN_VALUE;           // values can be negative: never start at 06        gain(root);7        return best;8    }9 10    /** Best downward path starting at node; also records the best path that bends at node. */11    private int gain(TreeNode node) {12        if (node == null) return 0;13        int left = Math.max(0, gain(node.left));          // a negative branch is worse than none14        int right = Math.max(0, gain(node.right));15        best = Math.max(best, node.val + left + right);   // path bending here uses both sides16        return node.val + Math.max(left, right);          // parent can extend only ONE side17    }18}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private int best;3 4    public int maxPathSum(TreeNode root) {5        best = Integer.MIN_VALUE;           // values can be negative: never start at 06        gain(root);7        return best;8    }9 10    /** Best downward path starting at node; also records the best path that bends at node. */11    private int gain(TreeNode node) {12        if (node == null) return 0;13        int left = Math.max(0, gain(node.left));          // a negative branch is worse than none14        int right = Math.max(0, gain(node.right));15        best = Math.max(best, node.val + left + right);   // path bending here uses both sides16        return node.val + Math.max(left, right);          // parent can extend only ONE side17    }18}

in the room

How to say it in the interview

talk track

Say: "This is Diameter with values instead of edge counts."
Explain clamping at 0: a negative branch is worse than not taking it — the same "restart" choice as Kadane's algorithm.
Explain why the return value uses only one side: a path can't fork.

traps

Initializing best to 0 — an all-negative tree like [-3] must return −3.
Returning node.val + left + right to the parent — that would make the path fork.

what they ask next

Follow-ups

Return the path itself?

Return the gain and remember which child gave it; at the best node, stitch left arm (reversed) + node + right arm.

before you submit

Edge cases to test

All values negative → the largest single value ([-3] → −3).
A negative child that must be dropped: [2,-1] → 2.
The best path lies wholly inside one subtree, far from the root.

practise next