Minimum Leaf Path Sum over All Roots
Updated
Problem statement
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[][]) → longExamples
Example 1
n = 6values = [4,1,2,3,5,6]edges = [[1,2],[1,3],[2,4],[2,5],[3,6]]return = 17With 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 = 6The 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 = 0A single node has no leaf other than the root, so the answer is 0.
Constraints
1 <= n <= 2 * 10^4values.length == n0 <= values[i] <= 10^4edges.length == n - 1edges[i].length == 21 <= a, b <= nanda != b- The edges form one tree that connects all
nnodes.
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