Make Costs of Paths Equal in a Binary Tree solution and explanation
9 more videos on this problem
Leetcode weekly contest 344 | 2673. Make Costs of Paths Equal in a Binary Tree | HindiPawan Kumar Giri · 14:08 · 1K views
Make Costs of Paths Equal in a Binary Tree | Weekly Contest 344codingMohan · 11:26 · 1K views
Leetcode 2673 Make Costs of Paths Equal in a Binary TreeThinkCode · 11:08 · 752 views
6419. Make Costs of Paths Equal in a Binary Tree - LEETCODE WEEKLY CONTEST 344 (Logic explained)Joyjit Codes · 5:23 · 586 views
Make Costs of Paths Equal in a Binary Tree - Leetcode 2673 - PythonAlgorithms Casts · 12:02 · 509 views
Leetcode 2673. Make Costs of Paths Equal in a Binary Tree | Weekly Contest 343 | weekly contestOffCampus Phodenge | Aman Chowdhury · 14:48 · 407 views
2673. Make Costs of Paths Equal in a Binary Tree (Leetcode Medium)Programming Live with Larry · 10:00 · 394 views
Leetcode 344 contest. problem 2673. Make Costs of Paths Equal in a Binary TreeAyush Rao · 12:00 · 211 views
2673. Make Costs of Paths Equal in a Binary Tree| Leetcode | Weekly Contest 344 | Easy DFS SolutionJeeetcode · 8:46 · 153 views
Leetcode 2673.|| Make Costs of Paths Equal in a Binary Tree || Leetcode Weekly Medium || cppKomal Pal · 10:54 · 93 views
The 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 the 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.
Example 1:
Input: n = 7, cost = [1,5,2,2,3,3,1] Output: 6 Explanation: We can do the following increments: - Increase the cost of node 4 one time. - Increase the cost of node 3 three times. - Increase the cost of node 7 two times. Each path from the root to a leaf will have a total cost of 9. The total increments we did is 1 + 3 + 2 = 6. It can be shown that this is the minimum answer we can achieve.
Example 2:
Input: n = 3, cost = [5,3,3] Output: 0 Explanation: The two paths already have equal total costs, so no increments are needed.
Constraints:
3 <= n <= 105n + 1is a power of2cost.length == n1 <= cost[i] <= 104
Approach overview
Problem Overview: You are given a complete binary tree represented by an array cost. Each node has a cost, and the goal is to make every root‑to‑leaf path have the same total cost. You can increment node values any number of times. The task is to compute the minimum number of increments required so all path sums become equal.
Approach 1: Recursive Bottom-Up DFS (Greedy) (Time: O(n), Space: O(h))
This approach processes the tree from the leaves upward using recursion. For each node, compute the total path cost coming from its left and right children. If the two subtree costs differ, you add the difference to the answer because you must increment the smaller side to match the larger one. Return the current node cost plus the larger subtree sum to the parent. The greedy insight: equalize paths locally at every node so the larger path propagates upward. This method naturally fits a postorder traversal of a tree or binary tree, ensuring each subtree is balanced before combining them.
Approach 2: Iterative Bottom-Up with Queue (Time: O(n), Space: O(n))
The iterative approach simulates the same bottom‑up idea without recursion. Because the tree is stored in an array, children of node i are 2*i and 2*i+1 (1-indexed). Start from the last internal node and move upward. For each node, compare the accumulated path costs of its two children, add the absolute difference to the answer, then update the parent cost by adding the larger child path. A queue or simple reverse traversal ensures children are processed before parents.
Recommended for interviews: The recursive greedy DFS is the solution most interviewers expect. It demonstrates strong understanding of postorder traversal and local balancing of subtree costs. The iterative array-based version proves you understand how complete binary trees map to arrays and how to simulate bottom‑up dynamic programming without recursion.
Approach 1: Recursive Approach
This approach involves recursively calculating the cost of each path from the root to the leaf and ensuring all paths have the same cost by incrementing node costs where necessary.
def minIncrements(n, cost):
path_cost = [0] * n
max_cost = 0
for i in range(n - 1, -1, -1):
if 2 * i + 1 < n:
path_cost[i] = cost[i] + max(path_cost[2 * i + 1], path_cost[2 * i + 2])
else:
path_cost[i] = cost[i]
max_cost = max(max_cost, path_cost[i])
increments = 0
for i in range(n):
increments += (max_cost - path_cost[i])
return increments
if __name__ == '__main__':
cost = [1, 5, 2, 2, 3, 3, 1]
print("Minimum increments required:", minIncrements(7, cost))import java.util.*;
public class Solution {
public int minIncrements(int n, int[] cost) {
int[] pathCost = new int[n];
int maxCost = 0;
for (int i = n - 1; i >= 0; --i) {
if (2 * i + 1 < n) {
pathCost[i] = cost[i] + Math.max(pathCost[2 * i + 1], pathCost[2 * i + 2]);
} else {
pathCost[i] = cost[i];
}
maxCost = Math.max(maxCost, pathCost[i]);
}
int increments = 0;
for (int i = 0; i < n; ++i) {
increments += (maxCost - pathCost[i]);
}
return increments;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] cost = {1, 5, 2, 2, 3, 3, 1};
System.out.println("Minimum increments required: " + solution.minIncrements(7, cost));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minIncrements(int n, vector<int>& cost) {
vector<int> pathCost(n);
int maxCost = 0;
for (int i = n - 1; i >= 0; --i) {
if (2 * i + 1 < n) {
pathCost[i] = cost[i] + max(pathCost[2 * i + 1], pathCost[2 * i + 2]);
} else {
pathCost[i] = cost[i];
}
maxCost = max(maxCost, pathCost[i]);
}
int increments = 0;
for (int i = 0; i < n; ++i) {
increments += (maxCost - pathCost[i]);
}
return increments;
}
int main() {
vector<int> cost = {1, 5, 2, 2, 3, 3, 1};
cout << "Minimum increments required: " << minIncrements(7, cost) << endl;
return 0;
}function minIncrements(n, cost) {
const pathCost = Array(n).fill(0);
let maxCost = 0;
for (let i = n - 1; i >= 0; --i) {
if (2 * i + 1 < n) {
pathCost[i] = cost[i] + Math.max(pathCost[2 * i + 1], pathCost[2 * i + 2]);
} else {
pathCost[i] = cost[i];
}
maxCost = Math.max(maxCost, pathCost[i]);
}
let increments = 0;
for (let i = 0; i < n; ++i) {
increments += (maxCost - pathCost[i]);
}
return increments;
}
const cost = [1, 5, 2, 2, 3, 3, 1];
console.log("Minimum increments required:", minIncrements(7, cost));#include <stdio.h>
#include <stdlib.h>
int minIncrements(int n, int* cost, int costSize) {
int maxCost = 0;
int* pathCost = (int*)calloc(n, sizeof(int));
for (int i = n - 1; i >= 0; --i) {
if ((2 * i + 1) < n) {
pathCost[i] = cost[i] + (pathCost[2 * i + 1] > pathCost[2 * i + 2] ? pathCost[2 * i + 1] : pathCost[2 * i + 2]);
} else {
pathCost[i] = cost[i];
}
if (pathCost[i] > maxCost) maxCost = pathCost[i];
}
int increments = 0;
for (int i = 0; i < n; ++i) {
increments += (maxCost - pathCost[i]);
}
free(pathCost);
return increments;
}
int main() {
int cost[] = {1, 5, 2, 2, 3, 3, 1};
int result = minIncrements(7, cost, 7);
printf("Minimum increments required: %d\n", result);
return 0;
}using System;
public class Solution {
public int MinIncrements(int n, int[] cost) {
int[] pathCost = new int[n];
int maxCost = 0;
for (int i = n - 1; i >= 0; --i) {
if (2 * i + 1 < n) {
pathCost[i] = cost[i] + Math.Max(pathCost[2 * i + 1], pathCost[2 * i + 2]);
} else {
pathCost[i] = cost[i];
}
maxCost = Math.Max(maxCost, pathCost[i]);
}
int increments = 0;
for (int i = 0; i < n; ++i) {
increments += (maxCost - pathCost[i]);
}
return increments;
}
public static void Main(string[] args) {
int[] cost = {1, 5, 2, 2, 3, 3, 1};
Solution solution = new Solution();
Console.WriteLine("Minimum increments required: " + solution.MinIncrements(7, cost));
}
}This Python solution adopts the same logic of calculating path costs using a reverse loop and utilizes Python lists for easy data management. It calculates the required increments by equalizing path costs.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Iterative Approach with Queue
This approach uses an iterative level-order traversal of the binary tree, utilizing a queue to manage nodes, while keeping track of path costs level-by-level.
def minIncrements(n, cost):
path_cost = cost[:]
total_increments = 0
for i in range(n - 1, 0, -2):
left_cost = path_cost[i - 1]
right_cost = path_cost[i]
parent_index = (i - 1) // 2
max_path_sum = max(left_cost, right_cost)
total_increments += (2 * max_path_sum - left_cost - right_cost)
path_cost[parent_index] += max_path_sum
return total_increments
if __name__ == '__main__':
cost = [1, 5, 2, 2, 3, 3, 1]
print("Minimum increments required:", minIncrements(7, cost))import java.util.*;
public class Solution {
public int minIncrements(int n, int[] cost) {
int[] pathCost = new int[n];
for (int i = 0; i < n; ++i) pathCost[i] = cost[i];
int maxCost = 0;
int totalIncrements = 0;
for (int i = n - 1; i > 0; i -= 2) {
int leftCost = pathCost[i - 1];
int rightCost = pathCost[i];
int parentIndex = (i - 1) / 2;
int maxPathSum = Math.max(leftCost, rightCost);
totalIncrements += (2 * maxPathSum - leftCost - rightCost);
pathCost[parentIndex] += maxPathSum;
}
return totalIncrements;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] cost = {1, 5, 2, 2, 3, 3, 1};
System.out.println("Minimum increments required: " + solution.minIncrements(7, cost));
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int minIncrements(int n, vector<int>& cost) {
vector<int> pathCost(n);
for (int i = 0; i < n; ++i) pathCost[i] = cost[i];
int maxCost = 0;
int totalIncrements = 0;
for (int i = n - 1; i > 0; i -= 2) {
int leftCost = pathCost[i - 1];
int rightCost = pathCost[i];
int parentIndex = (i - 1) / 2;
int maxPathSum = max(leftCost, rightCost);
totalIncrements += (2 * maxPathSum - leftCost - rightCost);
pathCost[parentIndex] += maxPathSum;
}
return totalIncrements;
}
int main() {
vector<int> cost = {1, 5, 2, 2, 3, 3, 1};
cout << "Minimum increments required: " << minIncrements(7, cost) << endl;
return 0;
}function minIncrements(n, cost) {
const pathCost = [...cost];
let totalIncrements = 0;
for (let i = n - 1; i > 0; i -= 2) {
const leftCost = pathCost[i - 1];
const rightCost = pathCost[i];
const parentIndex = Math.floor((i - 1) / 2);
const maxPathSum = Math.max(leftCost, rightCost);
totalIncrements += (2 * maxPathSum - leftCost - rightCost);
pathCost[parentIndex] += maxPathSum;
}
return totalIncrements;
}
const cost = [1, 5, 2, 2, 3, 3, 1];
console.log("Minimum increments required:", minIncrements(7, cost));#include <stdio.h>
#include <stdlib.h>
// Util function to find the maximum
int max(int a, int b) {
return (a > b) ? a : b;
}
int minIncrements(int n, int* cost, int costSize) {
int *pathCost = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
pathCost[i] = cost[i];
}
int maxCost = 0;
int totalIncrements = 0;
for (int i = n - 1; i > 0; i -= 2) {
int leftCost = pathCost[i - 1];
int rightCost = pathCost[i];
int parentIndex = (i - 1) / 2;
int maxPathSum = max(leftCost, rightCost);
totalIncrements += (2 * maxPathSum - leftCost - rightCost);
pathCost[parentIndex] += maxPathSum;
}
free(pathCost);
return totalIncrements;
}
int main() {
int cost[] = {1, 5, 2, 2, 3, 3, 1};
int result = minIncrements(7, cost, 7);
printf("Minimum increments required: %d\n", result);
return 0;
}using System;
public class Solution {
public int MinIncrements(int n, int[] cost) {
int[] pathCost = new int[n];
for (int i = 0; i < n; i++) pathCost[i] = cost[i];
int totalIncrements = 0;
for (int i = n - 1; i > 0; i -= 2) {
int leftCost = pathCost[i - 1];
int rightCost = pathCost[i];
int parentIndex = (i - 1) / 2;
int maxPathSum = Math.Max(leftCost, rightCost);
totalIncrements += (2 * maxPathSum - leftCost - rightCost);
pathCost[parentIndex] += maxPathSum;
}
return totalIncrements;
}
public static void Main(string[] args) {
int[] cost = {1, 5, 2, 2, 3, 3, 1};
Solution solution = new Solution();
Console.WriteLine("Minimum increments required: " + solution.MinIncrements(7, cost));
}
}The Python version copies the initial cost and iteratively computes max path sums, ensuring optimized adjustments of node costs up the binary tree.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Greedy Algorithm
According to the problem description, we need to calculate the minimum number of increments to make the path values from the root node to each leaf node equal.
The path values from the root node to each leaf node being equal is actually equivalent to the path values from any node as the root of a subtree to each leaf node of that subtree being equal.
Why is that? We can prove it by contradiction. Suppose there is a node x, and the path values from it as the root of a subtree to some leaf nodes are not equal. Then there exists a situation where the path values from the root node to the leaf nodes are not equal, which contradicts the condition "the path values from the root node to each leaf node are equal". Therefore, the assumption is not valid, and the path values from any node as the root of a subtree to each leaf node of that subtree are equal.
We can start from the bottom of the tree and calculate the number of increments layer by layer. For each non-leaf node, we can calculate the path values of its left and right child nodes. The number of increments is the difference between the two path values, and then update the path values of the left and right child nodes to the larger one of the two.
Finally, return the total number of increments.
The time complexity is O(n), where n is the number of nodes. The space complexity is O(1).
function minIncrements(n: number, cost: number[]): number {
let ans = 0;
for (let i = n >> 1; i; --i) {
const [l, r] = [i << 1, (i << 1) | 1];
ans += Math.abs(cost[l - 1] - cost[r - 1]);
cost[i - 1] += Math.max(cost[l - 1], cost[r - 1]);
}
return ans;
}func minIncrements(n int, cost []int) (ans int) {
for i := n >> 1; i > 0; i-- {
l, r := i<<1, i<<1|1
ans += abs(cost[l-1] - cost[r-1])
cost[i-1] += max(cost[l-1], cost[r-1])
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) |
| Iterative Approach with Queue | Time Complexity: O(n) |
| Greedy Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Bottom-Up DFS (Greedy) | O(n) | O(h) | Best general solution. Clean postorder traversal with minimal extra memory. |
| Iterative Bottom-Up with Queue | O(n) | O(n) | Useful when recursion depth is limited or when working directly with array-based trees. |
Frequently asked questions
Is Make Costs of Paths Equal in a Binary Tree easy or hard?
The problem is rated Medium difficulty on LeetCode with an acceptance rate around 58%. The main challenge is recognizing the greedy bottom‑up pattern. Once you identify that subtree path sums must be equalized locally, the implementation becomes straightforward.
Make Costs of Paths Equal in a Binary Tree Python/Java solution
In Python or Java, implement a recursive DFS that returns the maximum subtree path sum. At each node, compute left and right sums, add their absolute difference to a global counter, and return the node value plus the larger child sum. Both implementations run in O(n) time and require only recursion stack space.
How to solve Make Costs of Paths Equal in a Binary Tree in O(n)?
Process the tree bottom‑up using postorder traversal. For every node, compute the path sums of its left and right subtrees. Add the absolute difference between those sums to the total operations and return the node value plus the larger subtree sum. Since each node is visited once, the total runtime remains O(n).
What is the best approach for Make Costs of Paths Equal in a Binary Tree?
The optimal solution uses a greedy bottom‑up DFS. Traverse the tree in postorder, compute the path sums from the left and right children, and add the difference between them to the result. Propagate the larger subtree cost upward. This ensures all root‑to‑leaf paths become equal with the minimum number of increments in O(n) time.
Is Make Costs of Paths Equal in a Binary Tree asked at Google/Amazon/Meta?
Binary tree balancing and path sum equalization problems appear in interviews at companies like Google, Amazon, and Meta. Variations often test postorder traversal, greedy balancing, and tree dynamic programming. This problem is a good practice example for those patterns.
What data structure is used in Make Costs of Paths Equal in a Binary Tree?
The core data structure is a complete binary tree stored as an array. The algorithm performs a postorder traversal using recursion or a bottom‑up iteration. Greedy comparisons between left and right subtree sums ensure balanced path costs.
What is the time complexity of Make Costs of Paths Equal in a Binary Tree?
The optimal algorithm runs in O(n) time because every node in the binary tree is processed exactly once. Each step performs constant work: comparing child path sums and updating the result. Space complexity is O(h) for recursion stack depth, where h is the tree height.