DSA interview question

Binary Tree Maximum Path Sum

Medium · Algorithms · Topics: tree, dfs, dp

The problem

A trading network maps profit and loss onto a binary tree of positions (values may be negative), and an analyst wants the most profitable connected chain of positions: any path through parent–child links, starting and ending anywhere, with at least one node. At each node, the best path "bending" there is node + best downward gain on the left + best downward gain on the right, where a negative gain is replaced by 0, meaning that side isn't taken. The function returns the best single-branch gain upward, because a path can't fork on its way up to an ancestor.

Example: [-10, 9, 20, null, null, 15, 7] → 42 (15 → 20 → 7).

Function signature

int maxPathSum(TreeNode* root);  // non-empty tree

Test cases

Input (level order)	Output	Explanation
`[1, 2, 3]`	`6`	2 → 1 → 3
`[-10, 9, 20, null, null, 15, 7]`	`42`	15 → 20 → 7
`[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]`	`48`	7 → 11 → 4 → 5 → 8 → 13
`[2, -1]`	`2`	Skipping the negative child is better
`[-3]`	`-3`	At least one node must be used

(Confirm: the path is a sequence of distinct connected nodes, not necessarily through the root; values may be negative.)

How interviewers phrase it

"Given the root of a non-empty binary tree, return the maximum path sum of any non-empty path" (LeetCode 124).

Clarifying questions to ask

Must the path go through the root, or go downwards only? (Neither: any path.)
Can values be negative? (Yes.)
Must the path contain at least one node? (Yes, so an all-negative tree returns its largest value.)

Follow-ups to expect

"What does the helper return vs what does it record?"
"Why clamp gains at 0?"
"Why initialise the answer to −∞, not 0?"
"How is this like the diameter problem?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview