Watch 4 video solutions for Minimum Increments to Equalize Leaf Paths, a medium level problem involving Array, Dynamic Programming, Tree. This walkthrough by Code Thoughts has 1,284 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer n and an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an edge from node ui to vi .
Each node i has an associated cost given by cost[i], representing the cost to traverse that node.
The score of a path is defined as the sum of the costs of all nodes along the path.
Your goal is to make the scores of all root-to-leaf paths equal by increasing the cost of any number of nodes by any non-negative amount.
Return the minimum number of nodes whose cost must be increased to make all root-to-leaf path scores equal.
Example 1:
Input: n = 3, edges = [[0,1],[0,2]], cost = [2,1,3]
Output: 1
Explanation:
There are two root-to-leaf paths:
0 → 1 has a score of 2 + 1 = 3.0 → 2 has a score of 2 + 3 = 5.To make all root-to-leaf path scores equal to 5, increase the cost of node 1 by 2.
Only one node is increased, so the output is 1.
Example 2:
Input: n = 3, edges = [[0,1],[1,2]], cost = [5,1,4]
Output: 0
Explanation:
There is only one root-to-leaf path:
Path 0 → 1 → 2 has a score of 5 + 1 + 4 = 10.
Since only one root-to-leaf path exists, all path costs are trivially equal, and the output is 0.
Example 3:
Input: n = 5, edges = [[0,4],[0,1],[1,2],[1,3]], cost = [3,4,1,1,7]
Output: 1
Explanation:
There are three root-to-leaf paths:
0 → 4 has a score of 3 + 7 = 10.0 → 1 → 2 has a score of 3 + 4 + 1 = 8.0 → 1 → 3 has a score of 3 + 4 + 1 = 8.To make all root-to-leaf path scores equal to 10, increase the cost of node 1 by 2. Thus, the output is 1.
Constraints:
2 <= n <= 105edges.length == n - 1edges[i] == [ui, vi]0 <= ui, vi < ncost.length == n1 <= cost[i] <= 109edges represents a valid tree.Problem Overview: You are given a tree where each node contributes a cost to every root-to-leaf path passing through it. The goal is to perform the minimum number of increments on node values so that every root-to-leaf path has the same total sum.
Approach 1: Brute Force Path Balancing (O(n^2) time, O(n) space)
The straightforward idea is to compute the sum of every root-to-leaf path, determine the maximum path sum, and then increase nodes along smaller paths until they match the maximum. This requires enumerating all root-to-leaf paths using Depth-First Search. For each path, you repeatedly add increments to match the target sum. The drawback is that each adjustment may require re-traversing parts of the tree, leading to repeated work. This approach demonstrates the problem mechanics but becomes inefficient when the tree has many leaves.
Approach 2: Postorder DFS with Tree Dynamic Programming (O(n) time, O(h) space)
The optimal strategy processes the tree bottom-up using DFS and Dynamic Programming on a Tree. For each node, compute the maximum path cost from that node to any leaf in its subtree. When returning from the left and right children, compare their path sums. If one subtree is smaller, increment operations are required to match the larger subtree. Add the difference to the global operation count, effectively "balancing" the two branches. The node then returns its value plus the larger child path to its parent. This works because every imbalance is resolved locally while propagating the maximum achievable path upward. Each node is visited once, and only constant work is done per node, giving O(n) time complexity with O(h) recursion stack space, where h is the tree height.
Recommended for interviews: Interviewers expect the postorder DFS dynamic programming approach. Starting with the brute force explanation shows you understand the objective (equalizing root-to-leaf sums), but recognizing that subtree differences can be resolved locally using a bottom-up traversal demonstrates strong tree DP intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Path Balancing | O(n^2) | O(n) | Useful for understanding how path sums differ across leaves and for small trees |
| Postorder DFS Tree DP | O(n) | O(h) | Best general solution. Processes each node once and balances subtree path sums efficiently |