Skip to main content

21. Binary Tree Maximum Path Sum

hardAsked at JetBrains

Find the maximum path sum where a path is any node-to-node sequence — JetBrains uses this to test whether you can separate a recursive contribution from a global answer over an AST.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, return the maximum sum of any non-empty path. A path is a sequence of nodes connected by parent-child edges and may pass through the root but does not need to.

Constraints

  • 1 <= nodes <= 3 * 10^4
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root=[1,2,3]
Output
6

Example 2

Input
root=[-10,9,20,null,null,15,7]
Output
42

Approaches

1. Enumerate all paths

For each node, DFS outward to enumerate path sums; combinatorial explosion.

Time
O(n^2)
Space
O(n)
// for each node, run DFS in all directions and track best sum — explodes on balanced trees

Tradeoff:

2. Post-order DFS with global best

Each call returns the best one-armed path through that node, while updating a global best with the best two-armed path. Same separation of local contribution vs accumulated answer JetBrains inspections use on AST visitors.

Time
O(n)
Space
O(h)
function maxPathSum(root) {
  let best = -Infinity;
  const dfs = (n) => {
    if (!n) return 0;
    const l = Math.max(0, dfs(n.left));
    const r = Math.max(0, dfs(n.right));
    best = Math.max(best, n.val + l + r);
    return n.val + Math.max(l, r);
  };
  dfs(root);
  return best;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to separate 'what this node contributes upward' from 'best answer rooted here' explicitly — the same pattern their PSI walkers use when an inspection both reports findings and forwards a value.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Binary Tree Maximum Path Sum and other JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →