LeetCode Problem 2673

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy, Tree, Binary Tree

Solution

Edit

LeetCode 2673 - Make Costs of Paths Equal in a Binary Tree

Problem Understanding

This problem gives us a perfect binary tree with n nodes, where each node has an associated cost. The tree follows a strict indexing rule: node i has a left child at 2 * i and a right child at 2 * i + 1. Since the tree is perfect, every non leaf node has exactly two children and all leaves are located at the same depth.

The goal is to make the cost of every root to leaf path equal. A path cost is simply the sum of node values encountered from the root down to a leaf.

We are allowed to increment the cost of any node by 1, any number of times. The challenge is to determine the minimum total number of increments required so that all root to leaf path sums become identical.

An important detail is that we can only increase values, never decrease them. This means we must carefully balance path sums by raising smaller paths to match larger ones. Since increments affect all descendant paths of a node, deciding where to increment matters for minimizing the total cost.

The constraints reveal important information about the expected solution. Since n can be as large as 10^5, any solution worse than linear or near linear time will likely time out. A brute force simulation of repeatedly adjusting paths would be too expensive. The fact that the tree is perfect and represented implicitly as an array suggests there is likely a bottom up dynamic programming or greedy structure available.

Several edge cases are worth considering upfront. The smallest valid tree contains only three nodes, which means there are only two paths to compare. Another important case is when all path sums are already equal, in which case the answer should be 0. We should also consider highly unbalanced subtree costs where one side requires many increments to match the other. Fortunately, the problem guarantees a valid perfect binary tree, so we never need to handle missing children.

Approaches

Brute Force Approach

A naive strategy would be to explicitly compute every root to leaf path sum and repeatedly increment nodes in smaller paths until all paths match the largest path.

One way to do this would be:

1. Compute every root to leaf path sum.
2. Find the maximum path sum.
3. For every smaller path, determine how many increments are needed.
4. Try distributing increments across nodes while minimizing overlap.

This approach quickly becomes difficult because increments on internal nodes affect multiple paths simultaneously. A brute force search over all possible increment combinations would be exponential.

Even a simulation based approach becomes expensive because there can be up to O(n) leaf paths, each with O(log n) height, and repeatedly recalculating path sums leads to excessive overhead.

The brute force approach is conceptually correct because it eventually finds a valid equalization, but it is far too slow for n = 10^5.

Optimal Greedy Bottom Up Approach

The key insight is that we should process the tree from the leaves upward.

At every internal node, we compare the total path costs of its left and right subtrees.

If one subtree has a smaller path sum, we must increment it enough to match the larger subtree. Since we can only increase values, this adjustment is unavoidable and locally optimal.

Suppose:

• Left subtree path cost = L
• Right subtree path cost = R

Then:

• We add abs(L - R) to the answer.
• The parent contributes:

cost[parent] + max(L, R)

because after equalization both child paths become equal to the larger one.

This works because every subtree can be independently balanced before moving upward. Once a subtree is fixed, it behaves like a single equalized branch when viewed from its parent.

This naturally leads to a bottom up traversal using the array representation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or worse than O(n²)	O(n)	Tries adjusting path sums explicitly, too expensive
Optimal	O(n)	O(1)	Bottom up greedy balancing using subtree sums

Algorithm Walkthrough

1. Start from the last internal node and move upward toward the root.

Since leaves do not need processing, we begin at index n // 2 - 1 in zero based indexing. 2. For each internal node, identify its left and right children.

Using array indexing:

• Left child = 2 * i + 1
• Right child = 2 * i + 2

3. Compare the total costs of the left and right subtrees.

At this point, both children already represent fully balanced subtree path sums because we process bottom up. 4. Compute the difference between child subtree sums.

The minimum increments required at this node are:

abs(left_sum - right_sum)

This amount must be added to the answer because the smaller side must be increased to match the larger side. 5. Update the current node's effective subtree cost.

Since both child subtrees are now equalized to the larger value, the parent's subtree contribution becomes:

cost[i] += max(left_sum, right_sum)

6. Continue until reaching the root.

By the time we finish, every subtree has been balanced and the accumulated answer is the minimum number of increments.

Why it works

The correctness comes from a greedy invariant.

When processing a node, both child subtrees are already fully balanced internally. Therefore, the only remaining issue is balancing the two child path sums with each other.

Since costs can only increase, the minimum way to equalize two values is to raise the smaller one to match the larger one. Any other strategy would require at least as many increments.

Because every subtree is optimally solved before moving upward, the entire tree is optimally balanced.

Python Solution

from typing import List

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        total_increments = 0

        # Process from last internal node up to root
        for node_index in range(n // 2 - 1, -1, -1):
            left_child = 2 * node_index + 1
            right_child = 2 * node_index + 2

            left_cost = cost[left_child]
            right_cost = cost[right_child]

            # Add required increments to equalize children
            total_increments += abs(left_cost - right_cost)

            # Update current node with balanced subtree sum
            cost[node_index] += max(left_cost, right_cost)

        return total_increments

The implementation directly follows the bottom up idea.

We maintain a variable called total_increments to track the minimum operations required.

The loop starts from the last internal node and moves upward. Since the tree is perfect, every internal node always has two children, so child indexing is straightforward.

For every node, we compare the subtree costs stored at its children. Because we process bottom up, child values already represent fully balanced subtree path sums.

We add the difference between left and right subtree sums to the answer, since the smaller subtree must be increased.

Finally, we update the current node's cost by adding the larger subtree sum. This effectively compresses the subtree into a single balanced path cost for the parent.

By the time the root is processed, the answer contains the minimum total increments.

Go Solution

func minIncrements(n int, cost []int) int {
	totalIncrements := 0

	// Process from last internal node to root
	for nodeIndex := n/2 - 1; nodeIndex >= 0; nodeIndex-- {
		leftChild := 2*nodeIndex + 1
		rightChild := 2*nodeIndex + 2

		leftCost := cost[leftChild]
		rightCost := cost[rightChild]

		// Add increments needed to equalize children
		diff := leftCost - rightCost
		if diff < 0 {
			diff = -diff
		}

		totalIncrements += diff

		// Update parent subtree sum
		if leftCost > rightCost {
			cost[nodeIndex] += leftCost
		} else {
			cost[nodeIndex] += rightCost
		}
	}

	return totalIncrements
}

The Go implementation mirrors the Python version closely.

Since Go does not have built in abs() or max() functions for integers, we compute the absolute difference manually and use a conditional statement to select the larger subtree cost.

The solution modifies the cost slice in place, just like the Python version modifies the list. No additional memory allocation is required.

Integer overflow is not a concern here because the maximum accumulated path cost remains well within Go's integer range.

Worked Examples

Example 1

Input

n = 7
cost = [1,5,2,2,3,3,1]

Initial tree:

        1
      /   \
     5     2
    / \   / \
   2   3 3   1

We process bottom up.

Node	Left Cost	Right Cost	Increment Added	Updated Parent
3 (value 2)	2	3	1	5 + 3 = 8
2 (value 2)	3	1	2	2 + 3 = 5
1 (root)	8	5	3	1 + 8 = 9

Running total:

Step	Total Increments
After node 2	1
After node 1	3
After root	6

Final answer:

6

Example 2

Input

n = 3
cost = [5,3,3]

Tree:

    5
   / \
  3   3

Node	Left Cost	Right Cost	Increment Added	Updated Parent
Root	3	3	0	5 + 3 = 8

Total increments:

0

The paths are already balanced.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is processed exactly once
Space	O(1)	Only a few variables are used, modification happens in place

The algorithm is linear because every internal node is visited exactly once. Since a perfect binary tree has n total nodes and roughly n/2 internal nodes, the work scales proportionally with input size.

The space complexity is constant because no additional data structures are allocated. We reuse the input cost array to store subtree sums.

Test Cases

solution = Solution()

# Example 1
assert solution.minIncrements(7, [1, 5, 2, 2, 3, 3, 1]) == 6  # problem example

# Example 2
assert solution.minIncrements(3, [5, 3, 3]) == 0  # already balanced

# Smallest valid tree, imbalance
assert solution.minIncrements(3, [1, 2, 5]) == 3  # raise left subtree

# Perfectly balanced larger tree
assert solution.minIncrements(7, [1, 2, 2, 1, 1, 1, 1]) == 0

# Heavy imbalance in one subtree
assert solution.minIncrements(7, [1, 10, 1, 1, 1, 1, 1]) == 9

# All equal values
assert solution.minIncrements(15, [4] * 15) == 0

# Increasing costs
assert solution.minIncrements(
    7,
    [1, 2, 3, 4, 5, 6, 7]
) == 5  # multiple subtree adjustments

# Large values
assert solution.minIncrements(
    3,
    [10000, 1, 10000]
) == 9999  # large increment requirement

print("All tests passed!")

Test	Why
[1,5,2,2,3,3,1]	Validates core example
[5,3,3]	Checks already balanced tree
[1,2,5]	Smallest valid tree with imbalance
[1,2,2,1,1,1,1]	Confirms no unnecessary increments
[1,10,1,1,1,1,1]	Tests strong imbalance
[4] * 15	Validates larger balanced tree
[1,2,3,4,5,6,7]	Tests multiple adjustments
[10000,1,10000]	Verifies large numeric differences

Edge Cases

One important edge case is when the tree is already balanced. For example:

cost = [5,3,3]

A buggy implementation might accidentally add unnecessary increments or incorrectly recompute subtree sums. Our implementation correctly computes a difference of 0, so the answer remains unchanged.

Another important case is a heavily unbalanced subtree. Consider:

cost = [1,10,1]

The left subtree is much larger than the right subtree. Since we can only increase costs, the algorithm must raise the smaller subtree. Using abs(left - right) guarantees the exact required amount is added.

A third important edge case is when balancing must happen at multiple levels simultaneously. For example:

cost = [1,5,2,2,3,3,1]

The algorithm first fixes lower subtrees before propagating balanced sums upward. A top down implementation could make suboptimal decisions because it would not yet know the final subtree costs. Processing bottom up ensures every parent receives accurate balanced values.

Finally, the smallest valid input size of n = 3 is worth noting. Since there is only one internal node, the algorithm runs exactly one iteration and still behaves correctly without special handling.