Make Costs of Paths Equal in a Binary Tree

Make Costs of Paths Equal in a Binary Tree

What is this problem about?

In this problem, you are given an integer n representing a perfect binary tree with n nodes, numbered from 1 to n. You are also given an array cost where cost[i] is the cost of node i + 1. A path goes from the root to a leaf. Your goal is to make the total cost of all root-to-leaf paths exactly equal. You can only achieve this by increasing the cost of any node by 1. You must find the minimum number of increments required to equalize all paths.

Why is this asked in interviews?

This is an excellent problem to test a candidate's understanding of Bottom-Up Greedy Algorithms on Trees. Interviewers use it to see if you can recognize that fixing discrepancies at the leaf level is mathematically optimal because an increment at a leaf affects only one path, while an increment near the root affects many. It beautifully assesses tree traversal and dynamic summation logic.

Algorithmic pattern used

The best approach relies on a Post-Order Traversal (Bottom-Up Greedy) pattern. Because it's a perfect binary tree, the children of node i are located at indices 2 * i and 2 * i + 1. You iterate backwards from the last parent node (at index n/2) down to the root. For each parent, you look at its two children. To make the paths through both children equal, you must increment the smaller child's cost to match the larger child's cost. Add the difference to your total operations, and then pull the max cost up to the parent.

Example explanation

Assume a perfect tree with 3 nodes. n = 3. cost = [1, 5, 2]. Node 1 (root) has cost 1. Node 2 (left child) has cost 5. Node 3 (right child) has cost 2.

• We start at the lowest parent, which is node 1.
• Its children are node 2 (cost 5) and node 3 (cost 2).
• The path through the left is currently heavier. To equalize them, we must increase the right child's cost by 5 - 2 = 3.
• Operations required = 3.
• The cost to pass through node 1 and reach a leaf is now root_cost (1) + max(child_costs) -> 1 + 5 = 6. All paths from the root now have a cost of 6, and we used a minimum of 3 increments.

Common mistakes candidates make

A massive mistake is trying to calculate the total path sums from the root down (Top-Down DFS) and then trying to add differences. A top-down approach requires complex tracking of which nodes to increment to avoid over-adding. Another common error is using a physical Tree data structure. Since the tree is perfect and nodes are sequentially numbered, it is implicitly defined by the array indices; building actual Node objects wastes time and memory.

Interview preparation tip

When tackling the Make Costs of Paths Equal coding problem, remember the array representation of a perfect binary tree: parent is i, left child is 2*i, right child is 2*i + 1 (using 1-based indexing). Iterating backwards through the array naturally processes the tree from the bottom up, making the greedy logic incredibly concise.