2673. Make Costs of Paths Equal in a Binary Tree LeetCode Solution
In this guide, you will get 2673. Make Costs of Paths Equal in a Binary Tree LeetCode Solution with the best time and space complexity. The solution to Make Costs of Paths Equal in a Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Make Costs of Paths Equal in a Binary Tree
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.
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 <= 105
n + 1 is a power of 2
cost.length == n
1 <= cost[i] <= 104
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2673. Make Costs of Paths Equal in a Binary Tree LeetCode Solution in C++
class Solution {
public:
int minIncrements(int n, vector<int>& cost) {
int ans = 0;
for (int i = n / 2 - 1; i >= 0; --i) {
const int l = i * 2 + 1;
const int r = i * 2 + 2;
ans += abs(cost[l] - cost[r]);
// Record the information in the parent from the children. So, there's
// need to actually update the values in the children.
cost[i] += max(cost[l], cost[r]);
}
return ans;
}
}; /* code provided by PROGIEZ */
2673. Make Costs of Paths Equal in a Binary Tree LeetCode Solution in Java
class Solution {
public int minIncrements(int n, int[] cost) {
int ans = 0;
for (int i = n / 2 - 1; i >= 0; --i) {
final int l = i * 2 + 1;
final int r = i * 2 + 2;
ans += Math.abs(cost[l] - cost[r]);
// Record the information in the parent from the children. So, there's need to actually
// update the values in the children.
cost[i] += Math.max(cost[l], cost[r]);
}
return ans;
}
} // code provided by PROGIEZ
2673. Make Costs of Paths Equal in a Binary Tree LeetCode Solution in Python
class Solution:
def minIncrements(self, n: int, cost: list[int]) -> int:
ans = 0
for i in range(n // 2 - 1, -1, -1):
l = i * 2 + 1
r = i * 2 + 2
ans += abs(cost[l] - cost[r])
# Record the information in the parent from the children. So, there's need to actually
# update the values in the children.
cost[i] += max(cost[l], cost[r])
return ans # code by PROGIEZ
