# Make Costs of Paths Equal in a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/make-costs-of-paths-equal-in-a-binary-tree
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Tree, Binary Tree
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## 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:**

![](https://assets.glich.co/dsa/make-costs-of-paths-equal-in-a-binary-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/make-costs-of-paths-equal-in-a-binary-tree/image1.png) 

**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`

# Approaches
## Recursive Post-Order Traversal (DFS)
This approach utilizes a Depth First Search (DFS) to traverse the tree. It works in a post-order fashion, starting from the leaves and moving up to the root. For each internal node, it recursively calculates the costs of paths in its left and right subtrees, makes them equal by adding the difference to a running total, and then propagates the new, higher path cost up to its parent.
**Time:** O(n)

Each node in the tree is visited exactly once by the recursive function. Therefore, the time complexity is linear in the number of nodes. · **Space:** O(log n)

The space complexity is determined by the maximum depth of the recursion stack. Since the tree is a perfect binary tree with `n` nodes, its height is O(log n).
**Pros:** The recursive structure is a natural fit for tree problems and can be more intuitive to understand.; The logic directly follows the problem's recursive sub-structure.
**Cons:** Uses recursion, which incurs overhead from function calls.; The space complexity is O(log n) due to the recursion stack, which is less optimal than the iterative solution's O(1) space.
### Explanation
The problem asks for the minimum increments to make all root-to-leaf path costs equal. This can be achieved by ensuring that for any node, the path costs to any leaf in its left subtree are equal to the path costs to any leaf in its right subtree.

This suggests a bottom-up strategy. We can implement this using a recursive post-order traversal. We define a recursive function, say `dfs(nodeIndex)`, which calculates two things implicitly: the minimum increments needed for the subtree at `nodeIndex` and the cost of a path from `nodeIndex` to a leaf after equalization.

The function `dfs(nodeIndex)` will return the equalized path cost from `nodeIndex` to a leaf. A global or member variable will keep track of the total increments.

- **Base Case**: For a leaf node, no increments are needed within its subtree, and the path cost is its own cost.
- **Recursive Step**: For an internal node `p`, we first call `dfs` on its children `l` and `r`. This gives us the equalized path costs from `l` and `r` downwards, let's call them `cost_l` and `cost_r`. To make the paths through `p` equal, we must have `cost[p-1] + cost_l` equal to `cost[p-1] + cost_r` after some increments. This means `cost_l` and `cost_r` must be equalized. The minimum increment to do this is `abs(cost_l - cost_r)`. We add this to our total. The new path cost from `p` is `cost[p-1] + max(cost_l, cost_r)`. This value is returned to the caller (p's parent).

The initial call is `dfs(1)` for the root. The final answer is the total accumulated increments.

```java
class Solution {
    private int totalIncrements = 0;

    public int minIncrements(int n, int[] cost) {
        dfs(1, n, cost);
        return totalIncrements;
    }

    /**
     * Performs a post-order traversal to calculate path costs and increments.
     * @param i The current node index (1-based).
     * @param n The total number of nodes.
     * @param cost The array of costs.
     * @return The cost of the path from node i to a leaf after equalization.
     */
    private int dfs(int i, int n, int[] cost) {
        // Base case: if it's a leaf node (nodes from n/2 + 1 to n are leaves).
        // The children would be 2*i and 2*i+1. If 2*i > n, it's a leaf.
        if (i > n / 2) {
            return cost[i - 1];
        }

        // Children indices are 1-based.
        int leftChildIndex = 2 * i;
        int rightChildIndex = 2 * i + 1;

        // Recursively find the path costs for children subtrees.
        int leftPathCost = dfs(leftChildIndex, n, cost);
        int rightPathCost = dfs(rightChildIndex, n, cost);

        // The number of increments needed at this level is the absolute
        // difference between the path costs of the two children subtrees.
        totalIncrements += Math.abs(leftPathCost - rightPathCost);

        // The new path cost from this node 'i' is its own cost plus the
        // maximum of its children's path costs, as we increment the cheaper path.
        return cost[i - 1] + Math.max(leftPathCost, rightPathCost);
    }
}
```
### Algorithm
- Create a member variable `totalIncrements` initialized to 0 to accumulate the total increments.
- Define a recursive function `dfs(nodeIndex, n, cost)` that returns the total cost of a path from `nodeIndex` to a leaf in its subtree after equalization.
- In `dfs(nodeIndex)`:
  - **Base Case**: If `nodeIndex` represents a leaf node (i.e., `2 * nodeIndex > n`), it has no children. The path cost from itself is just its own cost, so return `cost[nodeIndex - 1]`.
  - **Recursive Step**: If `nodeIndex` is an internal node:
    - Recursively call `dfs` for the left child (`2 * nodeIndex`) and right child (`2 * nodeIndex + 1`) to get their respective equalized path costs, `leftPathCost` and `rightPathCost`.
    - The cost to make the two subtrees equal is the absolute difference between their path costs. Add this difference, `Math.abs(leftPathCost - rightPathCost)`, to the `totalIncrements`.
    - The new, unified path cost from `nodeIndex` downwards is its own cost plus the maximum of its children's path costs. Return `cost[nodeIndex - 1] + Math.max(leftPathCost, rightPathCost)`.
- To start the process, call `dfs(1, n, cost)` from the main function.
- The final answer is the accumulated value in `totalIncrements`.

## Bottom-up Iterative Approach
This is the most optimal approach, which uses an iterative, bottom-up strategy. It avoids recursion by iterating from the last level of parent nodes up to the root. For each parent, it calculates the necessary increments to equalize the path costs of its two children subtrees and updates the parent's cost in the array to reflect the new, equalized path cost. This allows the information to be propagated up the tree efficiently.
**Time:** O(n)

The algorithm iterates through the first `n/2` nodes of the tree (the parent nodes) exactly once. Each iteration involves a constant number of operations. Thus, the time complexity is linear with respect to `n`. · **Space:** O(1)

This approach uses a constant amount of extra space. It modifies the input `cost` array in-place to store intermediate path costs, thus not requiring any additional data structures that scale with the input size.
**Pros:** Extremely efficient with O(1) space complexity, as it modifies the input array in-place.; Iterative approach avoids recursion overhead and the risk of stack overflow on extremely deep trees.; Simple and concise implementation.
**Cons:** This approach modifies the input `cost` array, which might not be permissible in some scenarios (though it is fine for this problem).; The logic of iterating backwards from `n/2` might be slightly less intuitive than a direct recursive traversal for some developers.
### Explanation
The key insight is that for any parent node, the path costs to all leaves in its left subtree must be equal, and the same for its right subtree. To make all paths from the root equal, we must first satisfy this condition at every level, starting from the bottom.

We can iterate from the last parent node (`n/2`) up to the root (`1`). For each parent `i`, its children are `2*i` and `2*i+1`. By processing in this reverse order, when we are at node `i`, the values `cost[2*i - 1]` and `cost[2*i+1 - 1]` will have already been updated to represent the total path cost from that child node down to a leaf.

At each parent `i`, we compare the path costs from its two children. The difference `abs(cost_left - cost_right)` is the minimum amount we need to add to balance these two subtrees. This amount is added to our total increments. We then update the parent's cost `cost[i-1]` to be its original cost plus the maximum of the two children's path costs. This new value in `cost[i-1]` now represents the total path cost from node `i` to a leaf, which will be used when its own parent is processed.

This method cleverly reuses the input `cost` array to store the propagating path costs, achieving O(1) extra space.

```java
class Solution {
    public int minIncrements(int n, int[] cost) {
        int totalIncrements = 0;

        // The parent nodes in a perfect binary tree are from 1 to n/2.
        // We iterate backwards from the last parent up to the root.
        for (int i = n / 2; i >= 1; i--) {
            int leftChildIndex = 2 * i;
            int rightChildIndex = 2 * i + 1;

            // Array indices are 0-based, so we subtract 1.
            int leftPathCost = cost[leftChildIndex - 1];
            int rightPathCost = cost[rightChildIndex - 1];

            // The cost to make the paths from the children equal is their difference.
            totalIncrements += Math.abs(leftPathCost - rightPathCost);

            // Propagate the path cost up to the parent. The new path cost from the
            // parent is its own cost plus the maximum of the children's path costs.
            cost[i - 1] += Math.max(leftPathCost, rightPathCost);
        }

        return totalIncrements;
    }
}
```
### Algorithm
- Initialize a variable `totalIncrements` to 0.
- Iterate backwards through the parent nodes of the tree. In a perfect binary tree with nodes 1 to `n`, the parent nodes are numbered from `1` to `n/2`. So, the loop runs from `i = n/2` down to `1`.
- Inside the loop, for each parent node `i`:
  - Identify its left child `2*i` and right child `2*i+1`.
  - Retrieve the path costs from these children, which are stored in `cost[2*i - 1]` and `cost[2*i + 1 - 1]` respectively. Note that because we are iterating from the bottom up, these values represent the total path cost from that child to a leaf.
  - Calculate the absolute difference between the left and right path costs: `Math.abs(cost[2*i - 1] - cost[2*i - 1])`. Add this value to `totalIncrements`.
  - Update the parent's cost entry `cost[i-1]` to store the new total path cost from this parent to a leaf. This is done by adding the maximum of its children's path costs to its own cost: `cost[i-1] += Math.max(cost[2*i - 1], cost[2*i - 1])`.
- After the loop finishes, `totalIncrements` will hold the minimum total increments required. Return this value.

# Solutions
### Java

```java
class Solution {
private
  int[] cost;
private
  int n;
private
  int ans;
public
  int minIncrements(int n, int[] cost) {
    this.n = n;
    this.cost = cost;
    dfs(1);
    return ans;
  }
private
  int dfs(int i) {
    if ((i << 1) > n) {
      return cost[i - 1];
    }
    int l = dfs(i << 1);
    int r = dfs(i << 1 | 1);
    ans += Math.max(l, r) - Math.min(l, r);
    return cost[i - 1] + Math.max(l, r);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minIncrements(int n, vector<int> &cost) {
    int ans = 0;
    function<int(int)> dfs = [&](int i) -> int {
      if ((i << 1) > n) {
        return cost[i - 1];
      }
      int l = dfs(i << 1);
      int r = dfs(i << 1 | 1);
      ans += max(l, r) - min(l, r);
      return cost[i - 1] + max(l, r);
    };
    dfs(1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int: def dfs(i: int) -> int: if (i << 1) > n: return cost[i - 1] l, r = dfs(i << 1), dfs(i << 1 | 1) nonlocal ans ans += max(l, r) - min(l, r) return cost[i - 1] + max(l, r) ans = 0 dfs(1) return ans

```