Skip to main content

23. Binary Tree Maximum Path Sum

hardAsked at Palantir

A path in a binary tree is any sequence of nodes connected by edges; return the maximum sum across all such paths. Palantir asks this to see whether you separate the value RETURNED from a recursive call from the value RECORDED at each node — the same split they use when computing aggregated weights along ontology paths under row-level ACL.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir on-site loop — graded heavily on negative-value handling.
  • Blind (2025-12)— Reported as the on-site round-3 hard.
  • LeetCode Discuss (2026-02)— Tagged 'classic Palantir hard'.

Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can only appear in the sequence at most once. The path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Constraints

  • The number of nodes in the tree is in the range [1, 3 * 10^4].
  • -1000 <= Node.val <= 1000

Examples

Example 1

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

Explanation: Path 2 -> 1 -> 3 = 6.

Example 2

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

Explanation: Path 15 -> 20 -> 7 = 42.

Example 3

Input
root = [-3]
Output
-3

Approaches

1. Brute force enumerate paths

For every pair (u, v), compute the path sum from u to v via their LCA.

Time
O(n^2)
Space
O(n)
// O(n^2) — for every node u, DFS from u and try every endpoint v.
// Skipped here: it TLEs even on small trees and Palantir won't accept it.
function maxPathSum(root) {
  // ... O(n^2) skeleton omitted ...
  throw new Error('TLE');
}

Tradeoff: Quadratic — TLE on n=3*10^4. Mention briefly, then move on to the linear DP.

2. Single DFS with split return vs record

Each call returns max(node.val + best straight path through one child, 0). At each node, RECORD node.val + leftGain + rightGain into a global maximum — that handles V-shaped paths.

Time
O(n)
Space
O(h) recursion stack
function maxPathSum(root) {
  let best = -Infinity;
  function gain(node) {
    if (!node) return 0;
    const leftGain = Math.max(gain(node.left), 0);
    const rightGain = Math.max(gain(node.right), 0);
    const localBest = node.val + leftGain + rightGain;
    if (localBest > best) best = localBest;
    return node.val + Math.max(leftGain, rightGain);
  }
  gain(root);
  return best;
}

Tradeoff: Linear — every node visited once. The split between what's RETURNED (one-sided extension) and what's RECORDED (two-sided V-shape at the apex) is the entire trick. Don't forget the Math.max(_, 0) to drop negative contributions.

Palantir-specific tips

Palantir's grading rubric for this question is: (1) do you separate the recursive return from the recorded answer, and (2) do you handle all-negative trees correctly. State it out loud before coding: 'I'll return the best one-sided path from this node, but separately I'll RECORD the best two-sided path that bends here.' Bonus signal: connect to the ontology — aggregating weight along ancestor chains while clamping negatives is the same operation as computing access weight under inherited ACLs. The Math.max(_, 0) is the most common mistake — interviewers wait to see if you handle it.

Common mistakes

  • Initializing best = 0 — fails on all-negative trees where the answer is the least-negative node.
  • Returning the V-shape sum from the recursive call — that means the parent can't extend through, breaking the invariant.
  • Forgetting that gain(null) returns 0 — must be 0, not -Infinity, otherwise a leaf with positive value misbehaves.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

  • Diameter of binary tree (LC 543) — same shape but counting edges instead of summing values.
  • Longest path in a tree with edge weights — same DP.
  • Maximum path sum restricted to top-down (root-to-leaf) — simpler DP.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why initialize best to -Infinity instead of 0?

Because the tree might have all negative values. If best starts at 0, the algorithm would return 0 even when the correct answer is the largest single (negative) value.

Why is the recursive return value different from the recorded global?

Because a path that bends at a node (uses both children) can't extend upward through that node — it's already taken both branches. The recursion returns the BEST single-direction extension, while the global captures the BEST V-shape ending at any node.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →