Watch 10 video solutions for Make Costs of Paths Equal in a Binary Tree, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Pawan Kumar Giri has 1,100 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 + 1 is a power of 2cost.length == n1 <= cost[i] <= 104Problem 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 | 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. |