Optimal Path Sum in Binary Trees

You are in a Google interview, and the interviewer draws a binary tree on the whiteboard. Some nodes have negative values. "Find me the path with the largest sum," they say. "The path can start and end anywhere in the tree." You recognize this as Binary Tree Maximum Path Sum, a problem that consistently ranks among the hardest tree questions at companies like Citadel, Meta, and Amazon. The twist that makes it difficult: the path does not need to include the root, and it does not need to end at a leaf. That freedom creates a surprisingly tricky recursive subproblem.

TL;DR

Use post-order DFS. At each node, compute the maximum gain from the left and right subtrees (clamped to zero to discard negative contributions). Update a global maxSum with node.val + leftGain + rightGain, which represents the best path that "turns" at this node. Return node.val + max(leftGain, rightGain) to the parent, since a path cannot fork. This runs in O(n) time and O(h) space, where h is the tree height.

Why This Problem Matters

Binary Tree Maximum Path Sum combines several concepts that interviewers love to test together: recursive decomposition, global state management during DFS, and the subtle difference between what you return to a caller versus what you track as a candidate answer. If you can solve this cleanly, you are well-equipped for most tree problems that involve path aggregation, such as tree diameter, longest univalue path, or maximum width.

Understanding the Problem

A path in a binary tree is a sequence of connected nodes where each node appears at most once. The path sum is the total of all node values along that path. We need to find the highest possible path sum across all valid paths.

Key constraints:

• The tree has between 1 and 1000 nodes
• Node values range from -1000 to 1000
• The path must contain at least one node
• The path does not need to pass through the root
• The path does not need to end at a leaf

Here is a simple example:

For the tree [1, 2, 3], the optimal path uses all three nodes: 2 -> 1 -> 3, giving a sum of 6.

Now consider a more interesting tree where the root is negative:

For [-10, 9, 20, null, null, 15, 7], including the root (-10) would hurt the sum. The best path is 15 -> 20 -> 7, with a sum of 42. This path exists entirely within the right subtree.

Edge Cases to Consider

1. Single node: The path is just that node. If it is -3, the answer is -3.
2. All negative values: The answer is the least-negative node.
3. Skewed tree: The path may only use a contiguous portion of the chain.
4. Mixed positive and negative: Negative nodes may act as "bridges" worth crossing, or they may be worth skipping.

The Core Insight

At every node in the tree, there are three choices for forming a path that includes that node:

1. Just this node (neither child helps)
2. This node + left subtree path (extend leftward)
3. This node + right subtree path (extend rightward)
4. This node + both subtree paths (the path "turns" here)

Option 4 is the critical one. A path that goes left child -> node -> right child is valid because the path turns at the current node. This is the only place where we consider both children simultaneously. However, we cannot return this turning path to the parent. When reporting upward, the node can only extend through one child, because a path that already forks cannot be extended further.

This leads to a clean separation:

• Global update: maxSum = max(maxSum, node.val + leftGain + rightGain)
• Return to parent: node.val + max(leftGain, rightGain)

Solution Approach

Building the Algorithm

We perform a post-order DFS. At each node:

1. Recursively compute the maximum gain from the left child.
2. Recursively compute the maximum gain from the right child.
3. Clamp both gains to zero (discard negative contributions).
4. Compute the local path sum: node.val + leftGain + rightGain.
5. Update the global maximum if the local path sum is larger.
6. Return node.val + max(leftGain, rightGain) to the caller.

The base case is straightforward: a null node contributes a gain of 0.

Here is the recursive trace for our simple example [1, 2, 3]:

Node 2 is a leaf, so it returns 2. Node 3 is a leaf, so it returns 3. At node 1, the local path sum is 2 + 1 + 3 = 6, which updates maxSum to 6. We return 1 + max(2, 3) = 4 to the caller (though in this case, node 1 is the root, so no one uses that return value).

For the complex example [-10, 9, 20, null, null, 15, 7]:

At node 20, the path 15 + 20 + 7 = 42 updates maxSum to 42. Node 20 returns 20 + 15 = 35 upward. At node -10, the path 9 + (-10) + 35 = 34, which does not beat 42. The final answer is 42.

Implementation

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

import java.util.*;

public class Solution {

  public int maxPathSum(TreeNode root) {
    int[] maxSum = new int[1];
    maxSum[0] = Integer.MIN_VALUE;
    calculateMaxPathSum(root, maxSum);
    return maxSum[0];
  }

  private int calculateMaxPathSum(TreeNode node, int[] maxSum) {
    if (node == null) {
      return 0;
    }

    int leftMax = Math.max(0, calculateMaxPathSum(node.left, maxSum));
    int rightMax = Math.max(0, calculateMaxPathSum(node.right, maxSum));

    int currentMax = node.data + leftMax + rightMax;
    maxSum[0] = Math.max(maxSum[0], currentMax);

    return node.data + Math.max(leftMax, rightMax);
  }
}

Java uses an int[] array of size 1 to hold maxSum because primitive int arguments are passed by value. Wrapping it in an array lets the recursive helper modify the value visible to the caller.

Step-by-Step Walkthrough

For the tree [-10, 9, 20, null, null, 15, 7]:

Step 1: Recurse to node 9 (leaf). leftMax = 0, rightMax = 0. currentMax = 9. maxSum = 9. Return 9.

Step 2: Recurse to node 15 (leaf). currentMax = 15. maxSum = 15. Return 15.

Step 3: Recurse to node 7 (leaf). currentMax = 7. maxSum = 15. Return 7.

Step 4: At node 20. leftMax = 15, rightMax = 7. currentMax = 20 + 15 + 7 = 42. maxSum = 42. Return 20 + max(15, 7) = 35.

Step 5: At node -10. leftMax = max(0, 9) = 9, rightMax = max(0, 35) = 35. currentMax = -10 + 9 + 35 = 34. maxSum stays 42. Return -10 + 35 = 25.

Final answer: 42.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once during the DFS traversal. At each node, we do constant-time work: two comparisons, one addition, and one max update. The total work is proportional to the number of nodes.

Space Complexity: O(h)

The space comes entirely from the recursive call stack, where h is the height of the tree. For a balanced binary tree, h = O(log n). For a skewed tree (essentially a linked list), h = O(n). No additional data structures are used.

Common Pitfalls

1. Forgetting to clamp gains to zero: If you allow negative subtree gains to propagate, you will include paths that reduce the total sum. Always take max(0, childGain).

2. Returning the turning path instead of the single-direction path: The function must return node.val + max(leftGain, rightGain), not node.val + leftGain + rightGain. A forked path cannot be extended by the parent.

3. Initializing maxSum to zero: If all node values are negative, the answer is negative. Initialize to Integer.MIN_VALUE (or equivalent) so that any single node beats the initial value.

4. Confusing this with root-to-leaf path sum: This problem allows the path to start and end at any node. There is no requirement to reach a leaf or pass through the root.

Interview Tips

When this problem comes up in an interview:

1. Start with the small example: Draw [1, 2, 3] and note that the answer is 6. This establishes the basic idea.

2. Introduce the negative root case: Show [-10, 9, 20, null, null, 15, 7] and explain why the answer is 42, not 34. This demonstrates that you understand the path does not need to include the root.

3. Explain the two return values: Emphasize the distinction between the global update (turning path) and the return value (single-direction path). This is the central difficulty of the problem.

4. Talk through clamping: Explain why max(0, gain) is necessary. Use the example of a subtree with all negative values.

5. Discuss complexity: Mention O(n) time and O(h) space, and note the worst case for skewed trees.

6. Be ready for follow-ups:

   • "What if you also need to return the actual path?" (Track path nodes alongside the max sum.)
   • "What about an iterative solution?" (Post-order with a stack and a hash map, same complexity.)
   • "How does this relate to tree diameter?" (Same DFS pattern, but you maximize the number of edges instead of the node value sum.)

Key Takeaways

• The recursive function serves two purposes: it returns the best single-direction gain to the parent, and it updates a global maximum with the best turning path at the current node. Keeping these two concerns separate is what makes the solution work.
• Clamping child gains to zero (max(0, childGain)) lets the algorithm naturally skip subtrees that would reduce the path sum, which also handles the all-negative-values edge case correctly when combined with initializing maxSum to negative infinity.
• Post-order traversal is the natural fit because a node's computation depends on its children's results being available first.
• This O(n) time, O(h) space pattern of "compute from children, update a global, return to parent" appears in many tree problems including tree diameter, longest univalue path, and balanced tree checking.
• In interviews, draw two trees (a simple positive one and one with a negative root) and trace through the recursion to show the interviewer you understand why the path does not need to include the root.

Solutions in Other Languages

Python

class Solution:
    def max_path_sum(self, root):
        max_sum = float('-inf')

        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0

            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            current_path_sum = node.data + left_gain + right_gain
            max_sum = max(max_sum, current_path_sum)

            return node.data + max(left_gain, right_gain)

        max_gain(root)
        return max_sum

Python uses nonlocal to let the nested function modify max_sum from the enclosing scope. The float('-inf') initialization handles the all-negative-values case.

JavaScript

class Solution {
  maxPathSum(root) {
    let maxSum = -Infinity;

    function findMaxPath(node) {
      if (!node) return 0;

      const leftMax = Math.max(findMaxPath(node.left), 0);
      const rightMax = Math.max(findMaxPath(node.right), 0);

      const currentMaxPath = node.data + leftMax + rightMax;
      maxSum = Math.max(maxSum, currentMaxPath);

      return node.data + Math.max(leftMax, rightMax);
    }

    findMaxPath(root);
    return maxSum;
  }
}

TypeScript

class Solution {
  maxPathSum(root: TreeNode | null): number {
    let maxSum = -Infinity;

    const findMaxPath = (node: TreeNode | null): number => {
      if (!node) return 0;

      const leftMax = Math.max(findMaxPath(node.left), 0);
      const rightMax = Math.max(findMaxPath(node.right), 0);

      const currentMaxPath = node.data + leftMax + rightMax;
      maxSum = Math.max(maxSum, currentMaxPath);

      return node.data + Math.max(leftMax, rightMax);
    };

    findMaxPath(root);
    return maxSum;
  }
}

C++

#include <algorithm>
#include <limits.h>

class Solution {
public:
  int maxPathSum(TreeNode *root) {
    int maxSum = INT_MIN;
    maxPathSumHelper(root, maxSum);
    return maxSum;
  }

private:
  int maxPathSumHelper(TreeNode *node, int &maxSum) {
    if (!node) return 0;

    int leftMax = std::max(0, maxPathSumHelper(node->left, maxSum));
    int rightMax = std::max(0, maxPathSumHelper(node->right, maxSum));

    int currentMax = node->data + leftMax + rightMax;
    maxSum = std::max(maxSum, currentMax);

    return node->data + std::max(leftMax, rightMax);
  }
};

C++ passes maxSum by reference (int &maxSum), which avoids the need for a wrapper array or global variable.

Go

package solution

import "math"

func (s *Solution) MaxPathSum(root *TreeNode) int {
    maxSum := math.MinInt32

    var maxGain func(node *TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftGain := max(0, maxGain(node.Left))
        rightGain := max(0, maxGain(node.Right))

        priceNewPath := node.Data + leftGain + rightGain
        maxSum = max(maxSum, priceNewPath)

        return node.Data + max(leftGain, rightGain)
    }

    maxGain(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go uses a closure to capture maxSum by reference. The max helper is defined separately since Go's standard library did not include a generic max for integers until Go 1.21.

Scala

class Solution {
  def maxPathSum(root: TreeNode): Int = {
    var maxSum = Int.MinValue

    def maxGain(node: TreeNode): Int = {
      if (node == null) return 0

      val leftGain = Math.max(maxGain(node.left), 0)
      val rightGain = Math.max(maxGain(node.right), 0)

      val priceNewPath = node.data + leftGain + rightGain
      maxSum = Math.max(maxSum, priceNewPath)

      node.data + Math.max(leftGain, rightGain)
    }

    maxGain(root)
    maxSum
  }
}

Kotlin

class Solution {
  fun maxPathSum(root: TreeNode?): Int {
    val maxSum = IntArray(1)
    maxSum[0] = Int.MIN_VALUE
    calculateMaxPathSum(root, maxSum)
    return maxSum[0]
  }

  private fun calculateMaxPathSum(node: TreeNode?, maxSum: IntArray): Int {
    if (node == null) {
      return 0
    }

    val leftMax = maxOf(0, calculateMaxPathSum(node.left, maxSum))
    val rightMax = maxOf(0, calculateMaxPathSum(node.right, maxSum))

    val currentMax = node.data + leftMax + rightMax
    maxSum[0] = maxOf(maxSum[0], currentMax)

    return node.data + maxOf(leftMax, rightMax)
  }
}

Ruby

class Solution
  def max_path_sum(root)
    max_sum = [-Float::INFINITY]
    calculate_max_path_sum(root, max_sum)
    max_sum[0]
  end

  private

  def calculate_max_path_sum(node, max_sum)
    return 0 if node.nil?

    left_max = [0, calculate_max_path_sum(node.left, max_sum)].max
    right_max = [0, calculate_max_path_sum(node.right, max_sum)].max

    current_max = node.data + left_max + right_max
    max_sum[0] = [max_sum[0], current_max].max

    node.data + [left_max, right_max].max
  end
end

Ruby wraps max_sum in an array since Ruby passes primitives by value. The [a, b].max idiom is the standard way to compute the maximum of two values.

Rust

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

    fn calculate_max_path_sum(node: &Option<Box<TreeNode>>, max_sum: &mut i32) -> i32 {
        let node = match node {
            Some(n) => n,
            None => return 0,
        };

        let left_max = 0.max(Self::calculate_max_path_sum(&node.left, max_sum));
        let right_max = 0.max(Self::calculate_max_path_sum(&node.right, max_sum));

        let current_max = node.data + left_max + right_max;
        *max_sum = (*max_sum).max(current_max);

        node.data + left_max.max(right_max)
    }
}

Rust uses &mut i32 to pass max_sum by mutable reference. Pattern matching on Option<Box<TreeNode>> handles the null case idiomatically.

Swift

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

    @discardableResult
    private func calculateMaxPathSum(_ node: TreeNode?, _ maxSum: inout [Int]) -> Int {
        if node == nil {
            return 0
        }

        let leftMax = max(0, calculateMaxPathSum(node!.left, &maxSum))
        let rightMax = max(0, calculateMaxPathSum(node!.right, &maxSum))

        let currentMax = node!.data + leftMax + rightMax
        maxSum[0] = max(maxSum[0], currentMax)

        return node!.data + max(leftMax, rightMax)
    }
}

C#

public class Solution {
    public int MaxPathSum(TreeNode? root) {
        int[] maxSum = new int[1];
        maxSum[0] = int.MinValue;
        CalculateMaxPathSum(root, maxSum);
        return maxSum[0];
    }

    private int CalculateMaxPathSum(TreeNode? node, int[] maxSum) {
        if (node == null) {
            return 0;
        }

        int leftMax = Math.Max(0, CalculateMaxPathSum(node.left, maxSum));
        int rightMax = Math.Max(0, CalculateMaxPathSum(node.right, maxSum));

        int currentMax = node.data + leftMax + rightMax;
        maxSum[0] = Math.Max(maxSum[0], currentMax);

        return node.data + Math.Max(leftMax, rightMax);
    }
}

Dart

class Solution {
  int maxPathSum(TreeNode? root) {
    List<int> maxSum = [0];
    maxSum[0] = -1 << 31;
    _calculateMaxPathSum(root, maxSum);
    return maxSum[0];
  }

  int _calculateMaxPathSum(TreeNode? node, List<int> maxSum) {
    if (node == null) {
      return 0;
    }

    int leftMax = max(0, _calculateMaxPathSum(node.left, maxSum));
    int rightMax = max(0, _calculateMaxPathSum(node.right, maxSum));

    int currentMax = node.data + leftMax + rightMax;
    maxSum[0] = max(maxSum[0], currentMax);

    return node.data + max(leftMax, rightMax);
  }
}

PHP

class Solution {
    public function maxPathSum(TreeNode $root): int {
        $maxSum = [PHP_INT_MIN];
        $this->calculateMaxPathSum($root, $maxSum);
        return $maxSum[0];
    }

    private function calculateMaxPathSum(?TreeNode $node, array &$maxSum): int {
        if ($node === null) {
            return 0;
        }

        $leftMax = max(0, $this->calculateMaxPathSum($node->left, $maxSum));
        $rightMax = max(0, $this->calculateMaxPathSum($node->right, $maxSum));

        $currentMax = $node->data + $leftMax + $rightMax;
        $maxSum[0] = max($maxSum[0], $currentMax);

        return $node->data + max($leftMax, $rightMax);
    }
}

Practice Makes Perfect

Once you are comfortable with this problem, try these related challenges that use a similar "return one thing to parent, track another globally" DFS pattern:

• Diameter of a binary tree - maximize the number of edges through each node instead of the value sum
• Longest univalue path - same DFS structure, but only extend paths through matching values
• Balanced binary tree - return height to parent, track balance globally

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed offers at top companies. Whether you are targeting Citadel, Google, or Amazon, getting comfortable with recursive tree patterns like this one will pay dividends across the entire interview process.