FastPrepMinimum Leaf Path Sum over All Roots
Problems/Minimum Leaf Path Sum over All Roots

Minimum Leaf Path Sum over All Roots

Infosys logoInfosys● HardFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Infosys full-time online assessment. In a thread about the Infosys SP/DSE exam, a commenter listed this as Q3 with a full statement: for each possible root, total the root-to-leaf path sums that leave out the root, and report the smallest total.

The post gives no limits, no value range, and no rule for a one-node tree. Here n is at most 2 · 10^4, values are 0 to 10^4, a one-node tree gives 0, and a degree-1 node chosen as the root is not a leaf.

Our version is about 90% the same as the reported question.

You are given an undirected tree with n nodes, numbered from 1 to n. Node i has the value values[i - 1]. edges[i] = [a, b] means nodes a and b are joined by an edge.

Pick a node r and hang the tree from it, so r is the root. A leaf is a node other than r that has no children. For every leaf, take the path from r down to that leaf and add up the values of the nodes on it, not counting r itself. Let F(r) be the total of these sums over all leaves.

Return the smallest F(r) over all choices of the root r. When n = 1, there is no leaf, and the answer is 0.

Function

minLeafPathSum(n: int, values: int[], edges: int[][]) → long

Examples

Example 1

n = 6values = [4,1,2,3,5,6]edges = [[1,2],[1,3],[2,4],[2,5],[3,6]]return = 17

With root 1, the leaves are 4, 5, and 6. The path sums without the root are 1 + 3 = 4, 1 + 5 = 6, and 2 + 6 = 8, so F(1) = 18.

With root 5, the leaves are 4 and 6. The paths are 5 → 2 → 4 with sum 1 + 3 = 4 and 5 → 2 → 1 → 3 → 6 with sum 1 + 4 + 2 + 6 = 13, so F(5) = 17.

The other roots give F(2) = 20, F(3) = 24, F(4) = 19, and F(6) = 22. The smallest is 17.

Example 2

n = 4values = [1,2,3,4]edges = [[1,2],[2,3],[3,4]]return = 6

The tree is the line 1 - 2 - 3 - 4. With root 4, node 4 is the root, not a leaf, so the only leaf is 1. Its path sum is 3 + 2 + 1 = 6. With root 2, the leaves are 1 and 4, giving 1 + (3 + 4) = 8. Root 1 gives 9 and root 3 gives 7. The smallest is 6.

Example 3

n = 1values = [7]edges = []return = 0

A single node has no leaf other than the root, so the answer is 0.

Constraints

  • 1 <= n <= 2 * 10^4
  • values.length == n
  • 0 <= values[i] <= 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= a, b <= n and a != b
  • The edges form one tree that connects all n nodes.

More Infosys Online Assessment questions

  • Lowest Common Ancestor with a Changing RootOA · Seen Nov 2026
  • Split Array to Minimize the Largest SumOA · Seen Nov 2026
  • Cherry PickupOA · Seen Nov 2026
  • Lexicographically Smallest Grid Path with One Letter ChangeOA · Seen Nov 2026
  • Minimum Cost to Supply Water with Wells and PipesOA · Seen Nov 2026
  • Minimum Cost to Tile a Strip with Widths 1, 2, and 3OA · Seen Nov 2026
  • Minimum Rounds to Complete All TasksOA · Seen Nov 2026
  • Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
  • Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
  • Usable Water with Contaminated PillarsOA · Seen Oct 2026

Similar questions at other companies

  • Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
  • Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
  • Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
  • Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Distance Sums to Special Nodes in a Weighted TreeNutanix · ONSITE INTERVIEWNutanix interview questions
  • Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
  • Sum Dynamic Weighted Tree DistancesJuspay · OA
  • Binary Tree CamerasAmazon · OA · PHONE SCREEN
  • Special Diameter EndpointsAgoda · OAAgoda interview questions
  • Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
All Infosys interview questionsSee Infosys hiring insights
Saved
class Solution {
    public long minLeafPathSum(int n, int[] values, int[][] edges) {
        // Write your code here.
    }
}
Checking account…