Make Costs of Paths Equal in a Binary Tree

• 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.

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.

1class Solution {2    private int totalIncrements = 0;3 4    public int minIncrements(int n, int[] cost) {5        dfs(1, n, cost);6        return totalIncrements;7    }8 9    /**10     * Performs a post-order traversal to calculate path costs and increments.11     * @param i The current node index (1-based).12     * @param n The total number of nodes.13     * @param cost The array of costs.14     * @return The cost of the path from node i to a leaf after equalization.15     */16    private int dfs(int i, int n, int[] cost) {17        // Base case: if it's a leaf node (nodes from n/2 + 1 to n are leaves).18        // The children would be 2*i and 2*i+1. If 2*i > n, it's a leaf.19        if (i > n / 2) {20            return cost[i - 1];21        }22 23        // Children indices are 1-based.24        int leftChildIndex = 2 * i;25        int rightChildIndex = 2 * i + 1;26 27        // Recursively find the path costs for children subtrees.28        int leftPathCost = dfs(leftChildIndex, n, cost);29        int rightPathCost = dfs(rightChildIndex, n, cost);30 31        // The number of increments needed at this level is the absolute32        // difference between the path costs of the two children subtrees.33        totalIncrements += Math.abs(leftPathCost - rightPathCost);34 35        // The new path cost from this node 'i' is its own cost plus the36        // maximum of its children's path costs, as we increment the cheaper path.37        return cost[i - 1] + Math.max(leftPathCost, rightPathCost);38    }39}

• 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.

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.

1class Solution {2    public int minIncrements(int n, int[] cost) {3        int totalIncrements = 0;4 5        // The parent nodes in a perfect binary tree are from 1 to n/2.6        // We iterate backwards from the last parent up to the root.7        for (int i = n / 2; i >= 1; i--) {8            int leftChildIndex = 2 * i;9            int rightChildIndex = 2 * i + 1;10 11            // Array indices are 0-based, so we subtract 1.12            int leftPathCost = cost[leftChildIndex - 1];13            int rightPathCost = cost[rightChildIndex - 1];14 15            // The cost to make the paths from the children equal is their difference.16            totalIncrements += Math.abs(leftPathCost - rightPathCost);17 18            // Propagate the path cost up to the parent. The new path cost from the19            // parent is its own cost plus the maximum of the children's path costs.20            cost[i - 1] += Math.max(leftPathCost, rightPathCost);21        }22 23        return totalIncrements;24    }25}