Maximum sum path with negative numbers in a binary tree

You're sitting across from a Google interviewer who draws a binary tree on the whiteboard. Some of the node values are negative. "Find the path between any two nodes that gives you the maximum sum," they say. You realize immediately that the negative values change everything. You can't just greedily include every node. This is the binary tree maximum path sum problem, also known as "Binary Tree Maximum Path Sum" on other platforms, and it's a favorite at companies like Google and Facebook because it tests whether you can decompose a complex tree problem into a clean recursive solution.

TL;DR

Use a recursive helper that visits every node once. At each node, compute the best single-branch sum from the left and right subtrees, clamping negative contributions to zero. Track the global maximum by considering the current node as a "pivot" connecting both branches. The helper returns the best single-branch sum upward so the parent can extend the path. This runs in O(n) time and O(n) space.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

This problem sits at the intersection of recursion and optimization. It builds on simpler tree problems like finding height or computing subtree sums, but adds a twist that trips up many candidates: every node can be either helpful or harmful to your path. The technique you learn here, returning partial results upward while tracking a global optimum, shows up in problems like tree diameter, longest path in a DAG, and various interval scheduling challenges.

Understanding the Problem

Given the root of a binary tree where nodes contain both positive and negative integers, find the maximum sum along any path between two nodes. The path must follow parent-child edges, but it does not have to pass through the root.

Here is the example tree from the problem:

At first glance, you might think the maximum path goes through the root. After all, the root connects both subtrees. But the root here is -100, and including it would tank the sum. The optimal path actually avoids the root entirely:

The path 20 -> 90 -> 10 gives us a sum of 120. The root's -100 would drag the total down to 20, so the algorithm correctly skips it.

Constraints:

• Node values range from -10,000 to 10,000
• The path must follow tree edges (parent to child)
• The path does not need to pass through the root
• A path can consist of a single node

Edge Cases

1. Single node with negative value: The answer is that node's value (the path must include at least one node)
2. All negative values: Pick the least negative node
3. Tree with one branch: The path might use just part of that branch

The Pivot Insight

The key idea is that every node in the tree could potentially serve as the "pivot" of the maximum sum path. A pivot node is where the path turns, connecting a segment from the left subtree through the pivot and into the right subtree.

Consider this tree:

At node 3, the left subtree contributes max(0, -6) = 0 and the right subtree contributes 7. The pivot sum at node 3 is 0 + 3 + 7 = 10. But at node 1, the left subtree contributes max(0, search(-2)) and the right subtree contributes search(3). The algorithm evaluates every node as a potential pivot and keeps the best one.

This decomposition is what makes the problem tractable. Instead of trying every pair of nodes (which would be O(n^2)), we solve it in a single O(n) pass by recognizing that the optimal path must have exactly one pivot node.

Solution Approach

We need a recursive helper function, search, with two responsibilities:

1. Update the global maximum by treating the current node as a pivot (left + node + right)
2. Return the best single-branch sum so the parent can extend the path through this node

Why return a single-branch sum instead of the pivot sum? Because a parent node can only extend the path in one direction through its child. If node A is the parent of node B, the path through A can go through B's left subtree or B's right subtree, but not both. Both branches are only used when B itself is the pivot.

The critical detail for handling negative values: clamp each subtree's contribution to zero. If a subtree's best path sum is negative, we simply don't include it. This is done with Math.max(0, search(child)).

Let me trace through the example tree to show how the recursion unfolds:

Walking through the recursion bottom-up:

• Node 20: No children. Pivot sum = 20. Returns 20.
• Node 10: No children. Pivot sum = 10. Returns 10.
• Node 90 (right): leftMax = 20, rightMax = 10. Pivot sum = 20 + 90 + 10 = 120. maxSumHolder updated to 120. Returns max(90+20, 90+10) = 110.
• Node 90 (left): No children. Pivot sum = 90. Returns 90.
• Node -100: leftMax = 90, rightMax = 110. Pivot sum = 90 + (-100) + 110 = 100. maxSumHolder stays at 120 since 100 is smaller. Returns max(-100+90, -100+110) = 10.

The final answer is 120, found when the right child (90) was the pivot.

Why Initialize to Integer.MIN_VALUE?

Consider a tree with a single node of value -4:

If we initialized maxSumHolder to 0, we would never update it because the pivot sum (-4) is less than 0. We would incorrectly return 0 when the correct answer is -4. By starting at Integer.MIN_VALUE, any real node value will be larger, ensuring the first pivot sum always gets recorded.

Implementation

public class Solution {
  public int maxPathSumWithNeg(TreeNode root) {
    // Box the max sum in an array for pass-by-reference semantics
    int[] maxSumHolder = {Integer.MIN_VALUE};
    search(root, maxSumHolder);
    return maxSumHolder[0];
  }

  private int search(TreeNode node, int[] maxSumHolder) {
    if (node == null) return 0;

    // Clamp to 0: if a subtree is net-negative, skip it
    int leftMaxSum = Math.max(0, search(node.left, maxSumHolder));
    int rightMaxSum = Math.max(0, search(node.right, maxSumHolder));

    // Treat this node as the pivot of a potential max path
    maxSumHolder[0] = Math.max(
      maxSumHolder[0],
      node.data + leftMaxSum + rightMaxSum
    );

    // Return the best single-branch sum for the parent to use
    return Math.max(node.data + leftMaxSum, node.data + rightMaxSum);
  }
}

Three things to note in this code:

1. The array trick: Java passes primitives by value, so we wrap the max sum in an int[] to give the helper function a mutable reference. In Python you would use a list; in C++ you would use a pointer.

2. Clamping to zero: Math.max(0, search(...)) ensures we never include a subtree that would reduce the sum. This single line is what separates this problem from the positive-only variant.

3. Two different sums: The pivot sum (left + node + right) goes into maxSumHolder. The return value (node + max(left, right)) is a single-branch sum for the parent. Mixing these up is the most common bug.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node we do constant work: two recursive calls (which together cover all nodes), two max comparisons, and one update to maxSumHolder.

Space Complexity: O(n)

The space is dominated by the recursive call stack. In the worst case (a completely skewed tree where every node has only one child), the recursion depth equals n. For a balanced tree, the stack depth is O(log n).

Common Pitfalls

1. Returning the pivot sum instead of the single-branch sum: If your helper returns left + node + right, the parent will try to extend a path that already uses both branches of the child. This creates an invalid path that visits nodes more than once.

2. Forgetting to clamp negatives: Without Math.max(0, ...), a subtree with sum -50 would drag down every ancestor's path calculation. The clamp is essential for correctness with negative values.

3. Initializing maxSumHolder to zero: This fails when all nodes are negative. The answer would be the largest (least negative) single node, but you would return 0 instead.

4. Confusing this with root-to-leaf path sum: This problem allows the path to start and end at any two nodes, not just root to leaf. The pivot can be any internal node.

Interview Tips

When you get this problem in an interview:

1. Clarify the path definition: "Can the path start and end at any node, or must it go through the root?" This shows you understand the subtlety.

2. Start with the positive-only version: If the interviewer allows, sketch the simpler version first (where all values are positive), then explain what changes when negatives are introduced. This demonstrates structured problem-solving.

3. Draw the pivot diagram: Show a node with left and right subtrees and explain why the helper must return a single-branch sum. This is usually the hardest part for interviewers to assess, and getting it right signals strong recursive thinking.

4. Trace through a small example: Use the tree with -100 at the root. Walk through each recursive call and show how maxSumHolder gets updated to 120 at the right child.

5. Mention the connection to tree diameter: Both problems use the same "track global optimum while returning partial result" pattern. Bringing this up shows breadth of knowledge.

Solutions in Other Languages

Python

class Solution:
    def max_path_sum_with_neg(self, root):
        max_sum_holder = [float('-inf')]
        self.search(root, max_sum_holder)
        return max_sum_holder[0]

    def search(self, node, max_sum_holder):
        if node is None:
            return 0
        left_max_sum = max(0, self.search(node.left, max_sum_holder))
        right_max_sum = max(0, self.search(node.right, max_sum_holder))
        max_sum_holder[0] = max(
            max_sum_holder[0],
            node.data + left_max_sum + right_max_sum
        )
        return max(node.data + left_max_sum, node.data + right_max_sum)

JavaScript

class Solution {
  maxPathSumWithNeg(root) {
    const maxSumHolder = [Number.NEGATIVE_INFINITY];
    this.search(root, maxSumHolder);
    return maxSumHolder[0];
  }

  search(node, maxSumHolder) {
    if (node === null) return 0;
    const leftMaxSum = Math.max(0, this.search(node.left, maxSumHolder));
    const rightMaxSum = Math.max(0, this.search(node.right, maxSumHolder));
    maxSumHolder[0] = Math.max(
      maxSumHolder[0],
      node.data + leftMaxSum + rightMaxSum
    );
    return Math.max(node.data + leftMaxSum, node.data + rightMaxSum);
  }
}

TypeScript

class Solution {
  maxPathSumWithNeg(root: TreeNode | null): number {
    const maxSumHolder: number[] = [Number.NEGATIVE_INFINITY];
    this.search(root, maxSumHolder);
    return maxSumHolder[0];
  }

  search(node: TreeNode | null, maxSumHolder: number[]): number {
    if (node === null) return 0;
    const leftMaxSum = Math.max(0, this.search(node.left, maxSumHolder));
    const rightMaxSum = Math.max(0, this.search(node.right, maxSumHolder));
    maxSumHolder[0] = Math.max(
      maxSumHolder[0],
      node.data + leftMaxSum + rightMaxSum
    );
    return Math.max(node.data + leftMaxSum, node.data + rightMaxSum);
  }
}

C++

class Solution {
public:
  int maxPathSumWithNeg(TreeNode *root) {
    int maxSumHolder = INT_MIN;
    search(root, &maxSumHolder);
    return maxSumHolder;
  }

private:
  int search(TreeNode *node, int *maxSumHolder) {
    if (node == nullptr) return 0;
    int leftMaxSum = std::max(0, search(node->left, maxSumHolder));
    int rightMaxSum = std::max(0, search(node->right, maxSumHolder));
    *maxSumHolder = std::max(
      *maxSumHolder,
      node->data + leftMaxSum + rightMaxSum
    );
    return std::max(node->data + leftMaxSum, node->data + rightMaxSum);
  }
};

Go

func MaxPathSumWithNeg(root *TreeNode) int {
    maxSumHolder := math.MinInt64
    search(root, &maxSumHolder)
    return maxSumHolder
}

func search(node *TreeNode, maxSumHolder *int) int {
    if node == nil {
        return 0
    }
    leftMaxSum := int(math.Max(0, float64(search(node.Left, maxSumHolder))))
    rightMaxSum := int(math.Max(0, float64(search(node.Right, maxSumHolder))))
    *maxSumHolder = int(math.Max(
        float64(*maxSumHolder),
        float64(node.Data+leftMaxSum+rightMaxSum)))
    return int(math.Max(float64(node.Data+leftMaxSum), float64(node.Data+rightMaxSum)))
}

Scala

class Solution {
  def maxPathSumWithNeg(root: TreeNode): Int = {
    val maxSumHolder = Array(Int.MinValue)
    search(root, maxSumHolder)
    maxSumHolder(0)
  }

  private def search(node: TreeNode, maxSumHolder: Array[Int]): Int = {
    if (node == null) return 0
    val leftMaxSum = Math.max(0, search(node.left, maxSumHolder))
    val rightMaxSum = Math.max(0, search(node.right, maxSumHolder))
    maxSumHolder(0) = Math.max(maxSumHolder(0), node.data + leftMaxSum + rightMaxSum)
    Math.max(node.data + leftMaxSum, node.data + rightMaxSum)
  }
}

Kotlin

class Solution {
    fun maxPathSumWithNeg(root: TreeNode?): Int {
        val maxSumHolder = IntArray(1) { Int.MIN_VALUE }
        search(root, maxSumHolder)
        return maxSumHolder[0]
    }

    private fun search(node: TreeNode?, maxSumHolder: IntArray): Int {
        if (node == null) return 0
        val leftMaxSum = maxOf(0, search(node.left, maxSumHolder))
        val rightMaxSum = maxOf(0, search(node.right, maxSumHolder))
        maxSumHolder[0] = maxOf(maxSumHolder[0], node.data + leftMaxSum + rightMaxSum)
        return maxOf(node.data + leftMaxSum, node.data + rightMaxSum)
    }
}

Swift

class Solution {
    func maxPathSumWithNeg(_ root: TreeNode?) -> Int {
        var maxSumHolder = [Int.min]
        search(root, &maxSumHolder)
        return maxSumHolder[0]
    }

    @discardableResult
    private func search(_ node: TreeNode?, _ maxSumHolder: inout [Int]) -> Int {
        guard let node = node else { return 0 }
        let leftMaxSum = max(0, search(node.left, &maxSumHolder))
        let rightMaxSum = max(0, search(node.right, &maxSumHolder))
        maxSumHolder[0] = max(maxSumHolder[0], node.data + leftMaxSum + rightMaxSum)
        return max(node.data + leftMaxSum, node.data + rightMaxSum)
    }
}

Rust

impl Solution {
    pub fn max_path_sum_with_neg(&self, root: Option<Box<TreeNode>>) -> i32 {
        let mut max_sum = i32::MIN;
        Self::search(&root, &mut max_sum);
        max_sum
    }

    fn search(node: &Option<Box<TreeNode>>, max_sum: &mut i32) -> i32 {
        match node {
            None => 0,
            Some(current) => {
                let left_max_sum = std::cmp::max(0, Self::search(&current.left, max_sum));
                let right_max_sum = std::cmp::max(0, Self::search(&current.right, max_sum));
                *max_sum = std::cmp::max(*max_sum, current.data + left_max_sum + right_max_sum);
                std::cmp::max(current.data + left_max_sum, current.data + right_max_sum)
            }
        }
    }
}

C#

public class Solution {
    public int MaxPathSumWithNeg(TreeNode? root) {
        int[] maxSumHolder = { int.MinValue };
        Search(root, maxSumHolder);
        return maxSumHolder[0];
    }

    private int Search(TreeNode? node, int[] maxSumHolder) {
        if (node == null) return 0;
        int leftMaxSum = Math.Max(0, Search(node.left, maxSumHolder));
        int rightMaxSum = Math.Max(0, Search(node.right, maxSumHolder));
        maxSumHolder[0] = Math.Max(
            maxSumHolder[0],
            node.data + leftMaxSum + rightMaxSum
        );
        return Math.Max(node.data + leftMaxSum, node.data + rightMaxSum);
    }
}

Dart

class Solution {
  int maxPathSumWithNeg(TreeNode? root) {
    List<int> maxSumHolder = [-2147483648];
    _search(root, maxSumHolder);
    return maxSumHolder[0];
  }

  int _search(TreeNode? node, List<int> maxSumHolder) {
    if (node == null) return 0;
    int leftMaxSum = max(0, _search(node.left, maxSumHolder));
    int rightMaxSum = max(0, _search(node.right, maxSumHolder));
    maxSumHolder[0] = max(
      maxSumHolder[0],
      node.data + leftMaxSum + rightMaxSum
    );
    return max(node.data + leftMaxSum, node.data + rightMaxSum);
  }
}

Ruby

class Solution
  def max_path_sum_with_neg(root)
    max_sum_holder = [-Float::INFINITY]
    search(root, max_sum_holder)
    max_sum_holder[0]
  end

  def search(node, max_sum_holder)
    return 0 if node.nil?
    left_max_sum = [0, search(node.left, max_sum_holder)].max
    right_max_sum = [0, search(node.right, max_sum_holder)].max
    max_sum_holder[0] = [max_sum_holder[0], node.data + left_max_sum + right_max_sum].max
    node.data + [left_max_sum, right_max_sum].max
  end
end

PHP

class Solution {
    public function maxPathSumWithNeg(?TreeNode $root): int {
        $maxSum = PHP_INT_MIN;
        $this->search($root, $maxSum);
        return $maxSum;
    }

    private function search(?TreeNode $node, int &$maxSum): int {
        if ($node === null) return 0;
        $leftMaxSum = max(0, $this->search($node->left, $maxSum));
        $rightMaxSum = max(0, $this->search($node->right, $maxSum));
        $maxSum = max($maxSum, $node->data + $leftMaxSum + $rightMaxSum);
        return max($node->data + $leftMaxSum, $node->data + $rightMaxSum);
    }
}

Related Problems

Once you have this pattern down, try these related problems that use the same "return partial result, track global optimum" structure:

• Maximum sum path (positive only) - the simpler variant without negative values
• Diameter of binary tree - same recursive structure, but maximizing edge count instead of value sum
• Lowest common ancestor - another problem where the path between two arbitrary nodes matters

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job at a FAANG company, mastering recursive tree patterns like this will set you up for success.