Minimum Increments to Equalize Leaf Paths

Minimum Increments to Equalize Leaf Paths - Problem

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] = [u_i, v_i] indicates an edge from node u_i to v_i.

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.

Input & Output

Example 1 — Basic Tree

$ Input: n = 5, edges = [[0,1],[1,2],[1,3],[0,4]], cost = [1,2,3,4,5]

› Output: 2

💡 Note: Tree has paths: 0→1→2 (sum=6), 0→1→3 (sum=7), 0→4 (sum=6). Maximum sum is 7, so paths to nodes 2 and 4 need increments.

Example 2 — Balanced Tree

$ Input: n = 3, edges = [[0,1],[0,2]], cost = [1,1,1]

› Output: 0

💡 Note: Both paths 0→1 and 0→2 have equal sums (2), so no increments needed.

Example 3 — Single Node

$ Input: n = 1, edges = [], cost = [5]

› Output: 0

💡 Note: Only one node, no paths to equalize.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
0 ≤ u_i, v_i ≤ n - 1
1 ≤ cost[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with nodes having different costs

Calculate Path Sums

Find sums of all root-to-leaf paths

Identify Increments

Mark nodes on paths with less than maximum sum

Key Takeaway

🎯 Key Insight: Use DFS to find the maximum path sum, then count nodes on shorter paths that need increments

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use DFS to calculate maximum path sums in each subtree and count nodes that need increments during traversal. The optimal approach uses bottom-up DFS in O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Path Enumeration	O(n²)	O(n²)	Find all root-to-leaf paths, calculate their sums, then determine increments needed
Optimized DFS with Path Tracking	O(n)	O(n)	Single DFS traversal calculating maximum path sum and tracking nodes that need increments

Brute Force Path Enumeration — Algorithm Steps

Step 1: Build adjacency list from edges
Step 2: Use DFS to find all root-to-leaf paths
Step 3: Calculate sum for each path and find maximum
Step 4: For each path with sum < max, increment nodes to match

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from edges

Find Paths

DFS to enumerate all root-to-leaf paths

Calculate Sums

Sum costs for each path, find maximum

Mark Nodes

Mark all nodes on paths that need increments

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int paths[MAX_N][MAX_N];
int pathSizes[MAX_N];
int pathCount = 0;
int visited[MAX_N];

void dfs(int node, int parent, int path[], int pathSize, int cost[], int n) {
    path[pathSize++] = node;
    
    int isLeaf = 1;
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            isLeaf = 0;
            dfs(neighbor, node, path, pathSize, cost, n);
        }
    }
    
    if (isLeaf && node != 0) {
        for (int i = 0; i < pathSize; i++) {
            paths[pathCount][i] = path[i];
        }
        pathSizes[pathCount] = pathSize;
        pathCount++;
    }
}

int solution(int n, int edges[][2], int edgeCount, int cost[]) {
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    if (n == 1) return 0;
    
    // Find all root-to-leaf paths
    pathCount = 0;
    int path[MAX_N];
    dfs(0, -1, path, 0, cost, n);
    
    // Calculate path sums and find maximum
    int maxSum = 0;
    int pathSums[MAX_N];
    for (int i = 0; i < pathCount; i++) {
        int sum = 0;
        for (int j = 0; j < pathSizes[i]; j++) {
            sum += cost[paths[i][j]];
        }
        pathSums[i] = sum;
        if (sum > maxSum) maxSum = sum;
    }
    
    // Count nodes that need increment
    int nodesToIncrement[MAX_N] = {0};
    for (int i = 0; i < pathCount; i++) {
        if (pathSums[i] < maxSum) {
            for (int j = 0; j < pathSizes[i]; j++) {
                nodesToIncrement[paths[i][j]] = 1;
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (nodesToIncrement[i]) count++;
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Read edges (simplified parsing)
    int edges[MAX_N][2];
    int edgeCount = n - 1;
    char line[1000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small test cases
    char *ptr = line + 1; // skip [
    for (int i = 0; i < edgeCount; i++) {
        sscanf(ptr, "[%d,%d]", &edges[i][0], &edges[i][1]);
        while (*ptr != ']') ptr++;
        ptr += 2; // skip ],
    }
    
    // Read cost
    int cost[MAX_N];
    fgets(line, sizeof(line), stdin);
    ptr = line + 1; // skip [
    for (int i = 0; i < n; i++) {
        sscanf(ptr, "%d", &cost[i]);
        while (*ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    printf("%d\n", solution(n, edges, edgeCount, cost));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

DFS to find all paths takes O(n), and we may have O(n) paths, each requiring O(n) operations

⚠ Quadratic Growth

Space Complexity

O(n²)

Storing all paths can take O(n²) space in worst case (skewed tree)

⚠ Quadratic Space

58.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Path Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler