Maximum sum path in a binary tree

You're interviewing at Google and the interviewer draws a binary tree on the whiteboard. "Every node has a positive integer value," they say. "Find me the path between any two nodes that gives the largest sum." You pause, because this isn't the usual root-to-leaf path sum problem. The path can start and end anywhere. This is the Binary Tree Maximum Path Sum problem, also known as "Maximum Path Sum" on platforms like LeetCode (problem 124), and it's a favorite at companies like Facebook and Google because it tests whether you can think recursively about trees while managing global state.

TL;DR

Use a post-order DFS where each node returns its best single-branch sum upward. At every node, treat it as a potential "pivot" and check whether leftMax + node.data + rightMax beats the global maximum. Clamp negative subtree sums to zero so you never include a branch that hurts the total. This runs in O(n) time and O(n) space.

Why This Problem Matters

Maximum path sum sits at the intersection of tree traversal and optimization. It builds directly on simpler problems like finding tree height or root-to-leaf sums, but adds a twist: the path doesn't have to pass through the root, and it doesn't have to end at a leaf. Solving it requires you to reason about two different quantities at each node, a skill that transfers to problems like tree diameter, longest path in a DAG, and maximum subarray sum on trees.

Understanding the Problem

Given the root of a binary tree containing nodes with positive integer values, find the maximum sum obtainable by summing node values along a path between any two nodes. The path must follow parent-child connections, and each node can appear at most once.

Here is the example tree with nodes 1 through 7:

The maximum sum path is 5 -> 2 -> 1 -> 3 -> 7, giving us 5 + 2 + 1 + 3 + 7 = 18:

Notice the path doesn't include every node. Nodes 4 and 6 are excluded because including them would mean the path branches, and a valid path never forks.

Why Not Just Sum Everything?

In this example every value is positive, so you might wonder why we don't sum all seven nodes (28). A path must be a contiguous sequence of edges. You can't visit both children of a node and then continue upward, since that would create a fork. The path through 5-2-1-3-7 is the longest non-branching route with the highest sum.

Edge Cases

1. Single node: The answer is just that node's value.
2. Negative nodes: The optimal path may skip entire subtrees. Consider this tree:

The root is -10, but the best path is 15 -> 20 -> 7 = 42. The algorithm skips the -10 node and the 9 subtree entirely because including them would lower the sum.

3. Skewed tree: When nodes form a chain, the path might use the entire chain:

Here the best path is 41 -> 40 -> 4 -> 45 = 130.

The Pivot Node Insight

Every valid path in a binary tree has exactly one "highest" node, the node where the path transitions from climbing up to descending down. We call this the pivot node.

At the pivot, the maximum path sum through that node equals:

leftMaxSum + pivot.data + rightMaxSum

where leftMaxSum is the best sum obtainable going into the left subtree and rightMaxSum is the best sum going into the right subtree. If either subtree would contribute a negative sum, we clamp it to zero (effectively skipping that side).

The algorithm visits every node, computes its pivot sum, and keeps a running global maximum. Since every path has exactly one pivot, testing all nodes as pivots guarantees we find the optimal path.

What Each Node Returns to Its Parent

A node can't send both its left and right branch sums upward, because the parent's path can only extend through one child. So each node returns:

node.data + max(leftMaxSum, rightMaxSum)

This is the best single-branch sum starting at this node and going downward. The parent will use this value as either its leftMaxSum or rightMaxSum.

Implementation

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

public class Solution {
  public int maxPathSum(TreeNode root) {
    // Box the max sum in an array so the helper can update it by reference
    int[] maxSumHolder = {Integer.MIN_VALUE};
    search(root, maxSumHolder);
    return maxSumHolder[0];
  }

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

    // Get best single-branch sums from children, clamped to zero
    int leftMaxSum = Math.max(0, search(node.left, maxSumHolder));
    int rightMaxSum = Math.max(0, search(node.right, maxSumHolder));

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

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

A few things to notice:

• maxSumHolder is an int array of size 1. Java passes primitives by value, so wrapping the maximum in an array lets the helper method update it across recursive frames. In other languages you might use a mutable reference, a class field, or a closure variable.
• Clamping to zero with Math.max(0, ...) handles negative subtrees. If a child's best path sum is negative, we treat it as zero, which means "don't go into that subtree at all."
• The return value and the global update serve different purposes. The return value (node.data + max(left, right)) is the best single-branch sum for the parent. The global update (node.data + left + right) is the best through-path with this node as pivot.

Tracing the Recursion

Let's walk through the recursion on our example tree to see how maxSumHolder evolves:

At node 1, the pivot sum is 7 + 1 + 10 = 18, which becomes the final answer.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once during the post-order traversal. At each node we do a constant amount of work: two comparisons, one addition, and one max-update. Total work is proportional to the number of nodes.

Space Complexity: O(n)

The recursion depth equals the height of the tree. In the worst case (a completely skewed tree), the height is n, so the call stack uses O(n) space. For a balanced tree the depth is O(log n).

The one-element array maxSumHolder uses O(1) extra space, so the dominant factor is the call stack.

Common Pitfalls

1. Forgetting to clamp negative sums. Without Math.max(0, ...), a subtree with all negative values would drag down the path sum instead of being excluded.

2. Returning the pivot sum instead of the single-branch sum. The return value must be node.data + max(left, right), not node.data + left + right. Returning the through-path sum would let the parent build a branching path, which is invalid.

3. Initializing maxSumHolder to 0. If all nodes are negative, the answer is the least-negative node. Initializing to 0 would incorrectly report 0. Use Integer.MIN_VALUE instead.

4. Confusing this with root-to-leaf path sum. Root-to-leaf problems restrict where the path starts and ends. Here, any node can be an endpoint, which is why we need the pivot technique.

Interview Tips

When you see this problem in an interview:

1. Clarify the path definition. Ask whether the path must pass through the root (it doesn't) and whether it must end at leaves (it doesn't). These clarifications show you understand the problem's nuances.

2. Draw the pivot concept. Sketch a small tree and show that every path has exactly one highest node. This motivates the two-quantity approach (global max vs. return value) naturally.

3. Start with a simpler variant. If you're nervous, mention that you'd first solve the root-to-leaf version, then generalize. This shows structured thinking.

4. Discuss the negative-node edge case. Mention that clamping to zero handles negative subtrees. Interviewers often ask "what if some values are negative?" as a follow-up.

5. Mention iterative alternatives. You can solve this with an explicit stack doing post-order traversal. It avoids stack overflow on deep trees but is harder to code correctly under time pressure.

Solutions in Other Languages

Python

class Solution:
    def max_path_sum(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 node.data + max(left_max_sum, right_max_sum)

JavaScript

class Solution {
  maxPathSum(root) {
    const maxSumHolder = [-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 node.data + Math.max(leftMaxSum, rightMaxSum);
  }
}

TypeScript

class Solution {
  maxPathSum(root: TreeNode | null): number {
    const maxSumHolder: number[] = [-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 node.data + Math.max(leftMaxSum, rightMaxSum);
  }
}

C++

class Solution {
public:
  int maxPathSum(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 node->data + std::max(leftMaxSum, rightMaxSum);
  }
};

Go

func (s *Solution) MaxPathSum(root *TreeNode) int {
    maxSumHolder := []int{math.MinInt32}
    search(root, maxSumHolder)
    return maxSumHolder[0]
}

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[0] = int(math.Max(
        float64(maxSumHolder[0]),
        float64(node.Data+leftMaxSum+rightMaxSum),
    ))
    return node.Data + int(math.Max(float64(leftMaxSum), float64(rightMaxSum)))
}

Scala

class Solution {
  def maxPathSum(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)
    node.data + Math.max(leftMaxSum, rightMaxSum)
  }
}

Kotlin

class Solution {
  fun maxPathSum(root: TreeNode?): Int {
    val maxSumHolder = intArrayOf(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 node.data + maxOf(leftMaxSum, rightMaxSum)
  }
}

Swift

class Solution {
    func maxPathSum(_ 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 node.data + max(leftMaxSum, rightMaxSum)
    }
}

Ruby

class Solution
  def max_path_sum(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

Rust

impl Solution {
    pub fn max_path_sum(&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);
                current.data + std::cmp::max(left_max_sum, right_max_sum)
            }
        }
    }
}

C#

public class Solution {
    public int MaxPathSum(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 node.data + Math.Max(leftMaxSum, rightMaxSum);
    }
}

Dart

class Solution {
  int maxPathSum(TreeNode? root) {
    List<int> maxSumHolder = [(-1 << 31)];
    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 node.data + max(leftMaxSum, rightMaxSum);
  }
}

PHP

class Solution {
    public function maxPathSum(?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 $node->data + max($leftMaxSum, $rightMaxSum);
    }
}

Related Problems

Once you're comfortable with maximum path sum, these problems build on the same recursive-return-plus-global-update pattern:

• Diameter of a binary tree - Instead of summing values, count edges. The pivot logic is identical.
• Longest univalue path - Same structure, but only extend through nodes with matching values.
• Maximum sum of a subtree - A simpler variant where you sum entire subtrees rather than paths.
• Binary tree cameras - Uses a similar post-order DFS with state propagation.

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. If you want to build the kind of recursive thinking that problems like this demand, consistent practice with progressively harder tree problems is the most effective path.