Skip to main content
Talentd

Minimum Increments to Equalize Leaf Paths - Solution & Explanation

MediumArrayDynamic ProgrammingTreeDepth-First Search4 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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:

  • Path 0 → 1 has a score of 2 + 1 = 3.
  • Path 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:

  • Path 0 → 4 has a score of 3 + 7 = 10.
  • Path 0 → 1 → 2 has a score of 3 + 4 + 1 = 8.
  • Path 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 <= 105
  • edges.length == n - 1
  • edges[i] == [ui, vi]
  • 0 <= ui, vi < n
  • cost.length == n
  • 1 <= cost[i] <= 109
  • The input is generated such that edges represents a valid tree.

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Path BalancingO(n^2)O(n)Useful for understanding how path sums differ across leaves and for small trees
Postorder DFS Tree DPO(n)O(h)Best general solution. Processes each node once and balances subtree path sums efficiently

Video Solution

Minimum Increments to Equalize Leaf Paths | LeetCode contest 455| leetcode 3593| WEEKLY CONTEST 455 • Code Thoughts • 1,356 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Minimum Increments to Equalize Leaf Paths easy or hard?
Minimum Increments to Equalize Leaf Paths is typically categorized as a medium difficulty problem. The challenge lies in recognizing the bottom-up tree dynamic programming pattern and resolving subtree imbalances during a single DFS traversal.
Minimum Increments to Equalize Leaf Paths Python/Java solution
Implement a recursive DFS that returns the maximum path sum from each node to its leaves. Track a global variable for increments and add the absolute difference between left and right subtree sums at every node. The same logic works across Python, Java, C++, and Go with identical O(n) complexity.
How to solve Minimum Increments to Equalize Leaf Paths in O(n)?
Traverse the tree using postorder DFS. For every node, compute the maximum root-to-leaf path from its left and right children. If the child path sums differ, add the difference to the total increments needed to equalize them. Return the node value plus the larger child path sum to the parent, ensuring the subtree stays balanced.
What is the best approach for Minimum Increments to Equalize Leaf Paths?
The most efficient solution uses a postorder Depth-First Search with dynamic programming on the tree. For each node, compute the maximum path sum from its children and add the difference between left and right subtree costs as required increments. This balances subtree paths locally while propagating the maximum path upward. The algorithm runs in O(n) time.
Is Minimum Increments to Equalize Leaf Paths asked at Google/Amazon/Meta?
Tree dynamic programming and DFS balancing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of equalizing path sums or balancing subtree costs test a candidate's understanding of tree traversal and bottom-up aggregation logic.
What data structure is used in Minimum Increments to Equalize Leaf Paths?
The problem primarily uses a tree data structure combined with Depth-First Search. The solution also applies dynamic programming on the tree where each recursive call returns the maximum subtree path sum while accumulating increment operations.
What is the time complexity of Minimum Increments to Equalize Leaf Paths?
The optimal DFS dynamic programming solution runs in O(n) time because each node is processed exactly once. Only constant work is performed per node when comparing left and right subtree path sums. The space complexity is O(h) due to the recursion stack, where h is the tree height.

Ready to solve this problem?

Practice Minimum Increments to Equalize Leaf Paths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays