FastPrepMaximum Sum Path Between Two Leaf Nodes
Problems/Maximum Sum Path Between Two Leaf Nodes

Maximum Sum Path Between Two Leaf Nodes

Google logoGoogle● HardINTERNOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The visible source gives the leaf-to-leaf objective but omits the callable interface, examples, bounds, and behavior for trees with fewer than two leaves. This practice contract assumes at least two leaves and matches the reported core task at about 95%.

Given the root of a binary tree whose nodes contain integer values, return the maximum sum of the node values along a simple path whose two endpoints are distinct leaves.

A leaf is a node with no children. The input is guaranteed to contain at least two leaves, so a valid leaf-to-leaf path always exists.

The path may pass through any common ancestor, does not need to pass through the root, and may contain negative values. Its sum includes both leaf endpoints and every intermediate node.

Function

maxLeafToLeafPathSum(root: TreeNode) → long

Examples

Example 1

root = [1,2,3]return = 6

The only leaf-to-leaf path is 2 - 1 - 3, whose node values sum to 6.

Example 2

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

The maximum path is 15 - 20 - 7, whose node values sum to 42. It does not pass through the root.

Example 3

root = [-1,-2,-3]return = -6

All values are negative, but the path must still connect the two leaves. The path -2 - -1 - -3 sums to -6.

Constraints

  • The tree contains between 3 and 100000 nodes, inclusive.
  • -10^9 <= node.val <= 10^9
  • The tree contains at least two distinct leaves.
  • Every leaf-to-leaf path sum fits in a signed 64-bit integer.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public long maxLeafToLeafPathSum(TreeNode root) {
      // Write your code here.
    }

}
Checking account…