Make Costs of Paths Equal in a Binary Tree - Solution & Explanation
Problem Statement
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.
We create an array to store the cumulative path costs from each node to the leaves. Starting from the last node, we calculate the path cost by checking the costs from its child nodes. This ensures we have path costs for all root to leaf paths. The maximum path cost is then used to calculate the number of increments needed to make all paths equal.
Complexity
Time Complexity: O(n) as each node is processed once.
Space Complexity: O(n) to store path costs.
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.
This implementation iteratively calculates the maximum path costs using a straightforward loop. We gather costs up the tree while modifying increment counts through a greedy approach, which ensures each node's child paths are maximized efficiently.
Complexity
Time Complexity: O(n) as each node is checked once.
Space Complexity: O(n) for path cost storage.
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) as each node is processed once. |
| Iterative Approach with Queue | Time Complexity: O(n) as each node is checked once. |
| Greedy Algorithm | — |
Detailed 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. |
Video Solution
Leetcode weekly contest 344 | 2673. Make Costs of Paths Equal in a Binary Tree | Hindi • Pawan Kumar Giri • 1,113 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Costs of Paths Equal in a Binary Tree easy or hard?
Make Costs of Paths Equal in a Binary Tree Python/Java solution
How to solve Make Costs of Paths Equal in a Binary Tree in O(n)?
What is the best approach for Make Costs of Paths Equal in a Binary Tree?
Is Make Costs of Paths Equal in a Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Make Costs of Paths Equal in a Binary Tree?
What is the time complexity of Make Costs of Paths Equal in a Binary Tree?
Ready to solve this problem?
Practice Make Costs of Paths Equal in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode