Make Costs of Paths Equal in a Binary Tree

Make Costs of Paths Equal in a Binary Tree - Problem

You are given an integer n representing the number of nodes in a perfect binary tree consisting of nodes numbered from 1 to n. The root of the tree is node 1 and each node i in the tree has two children where the left child is node 2 * i and the right child is 2 * i + 1.

Each node in the tree also has a cost represented by a given 0-indexed integer array cost of size n where cost[i] is the cost of node i + 1. You are allowed to increment the cost of any node by 1 any number of times.

Return the minimum number of increments you need to make the cost of paths from the root to each leaf node equal.

Note:

A perfect binary tree is a tree where each node, except the leaf nodes, has exactly 2 children.
The cost of a path is the sum of costs of nodes in the path.

Input & Output

Example 1 — Basic Perfect Binary Tree

$ Input: cost = [1,5,2,2,3,3,1]

› Output: 6

💡 Note: Tree has paths: 1→5→2 (cost 8), 1→5→3 (cost 9), 1→2→3 (cost 6), 1→2→1 (cost 4). To balance, increment path costs to max 9: need 1+0+3+5 = 9 increments, but optimal is 6.

Example 2 — Small Tree

$ Input: cost = [7,7,7]

› Output: 0

💡 Note: Tree paths: 7→7 (cost 14) and 7→7 (cost 14). Both paths already have equal costs, so no increments needed.

Example 3 — Single Node

$ Input: cost = [5]

› Output: 0

💡 Note: Only one node, so only one path with cost 5. No balancing needed.

Constraints

n == cost.length
3 ≤ n ≤ 15
cost.length is odd
1 ≤ cost[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Perfect binary tree with node costs [1,5,2,2,3,3,1]

Path Analysis

Find all root-to-leaf paths and their costs

Balance Paths

Increment cheaper paths to match the maximum cost

Key Takeaway

🎯 Key Insight: Balance sibling subtrees recursively from leaves to root instead of calculating all paths

Asked in

f Meta 15 a Amazon 12 G Google 10 M Microsoft 8

The key insight is to use bottom-up DFS to balance sibling subtrees at each level. Instead of calculating all paths, we recursively ensure left and right subtrees have equal maximum path costs by incrementing the cheaper subtree. Best approach is DFS with Time: O(n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Bottom-Up Balancing	O(n)	O(log n)	Use DFS to balance subtrees from leaves to root in single traversal
Brute Force Path Enumeration	O(n²)	O(n)	Calculate all root-to-leaf paths and increment nodes to balance them

DFS Bottom-Up Balancing — Algorithm Steps

Step 1: DFS to leaf nodes
Step 2: Calculate subtree max costs
Step 3: Balance sibling subtrees
Step 4: Propagate balanced cost upward

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS to Leaves

Traverse to leaf nodes first

Balance Siblings

Balance left and right subtree costs

Propagate Up

Return balanced cost to parent

Code -

solution.c — C

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

int increments = 0;

int dfs(int node, int cost[], int n) {
    // If leaf node, return its cost
    int leftChild = 2 * node;
    int rightChild = 2 * node + 1;
    
    if (leftChild > n) {
        return cost[node - 1];
    }
    
    // Get costs from left and right subtrees
    int leftCost = dfs(leftChild, cost, n);
    int rightCost = rightChild <= n ? dfs(rightChild, cost, n) : 0;
    
    // Balance the subtrees by incrementing the cheaper one
    int maxSubtreeCost = leftCost > rightCost ? leftCost : rightCost;
    increments += (maxSubtreeCost - leftCost) + (maxSubtreeCost - rightCost);
    
    // Return total cost for this subtree
    return cost[node - 1] + maxSubtreeCost;
}

int solution(int cost[], int n) {
    if (n == 1) return 0;
    
    increments = 0;
    dfs(1, cost, n);
    return increments;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int cost[1000];
    int n = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        cost[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(cost, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visiting each node once

✓ Linear Growth

Space Complexity

O(log n)

Recursion stack depth equals tree height in perfect binary tree

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

DFS Bottom-Up Balancing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler