We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Costs of Paths Equal in a Binary Tree

Number: 2780

Difficulty: Medium

Paid? No

Companies: TikTok, DE Shaw

Problem Description

Given a perfect binary tree with n nodes (numbered from 1 to n) and a 0-indexed cost array where cost[i] represents the cost of node i+1, you are allowed to increment the cost of any node by 1 any number of times. The goal is to perform the minimum number of increments such that all paths from the root to each leaf have the same total cost.

Key Insights

  • The perfect binary tree structure (each non-leaf node has exactly 2 children) allows a neat DFS/post-order traversal.
  • For each non-leaf node, the cost discrepancies between its two children's root-to-leaf paths must be balanced.
  • By incrementing the subtree path that has a lower sum, you can make both child paths equal.
  • A bottom-up traversal lets you propagate the balanced path values upward, simultaneously keeping track of the number of increments needed.

Space and Time Complexity

Time Complexity: O(n) – We visit each node once. Space Complexity: O(n) in the worst-case scenario due to recursion stack space (O(log n) for a balanced tree).

Solution

We use a DFS (post-order) approach starting at the root. For leaf nodes, simply return the node’s cost. For non-leaf nodes, recursively compute the balanced path sums for the left and right children. At each node:

  1. Calculate the increments required to balance the two children’s sums by taking the difference.
  2. Update a global counter with these increments.
  3. Return the sum of the node’s own cost and the maximum of its two balanced child path sums, so that the subtree from this node is balanced. This approach guarantees minimal increments as we always only "fill the gap" on the lower cost path.

Code Solutions

# Python Solution with inline comments

class Solution:
    def minIncrements(self, n: int, cost: list[int]) -> int:
        self.total_increments = 0  # Global counter for increments
        
        # Helper function: performs DFS starting at node index 'i'
        def dfs(i: int) -> int:
            # Compute left child index and right child index based on perfect binary tree property
            left = 2 * i
            right = 2 * i + 1
            
            # If the node is a leaf (its children exceed n), simply return its cost
            if left > n:  # No children means leaf node
                return cost[i - 1]
            
            # Recursively balance left and right subtrees
            left_sum = dfs(left)
            right_sum = dfs(right)
            
            # Add increments to balance both subtrees
            self.total_increments += abs(left_sum - right_sum)
            
            # Return current node cost plus the maximum sum of the two balanced paths
            return cost[i - 1] + max(left_sum, right_sum)
        
        dfs(1)  # Start DFS from the root (node 1)
        return self.total_increments

# Example usage:
# sol = Solution()
# print(sol.minIncrements(7, [1,5,2,2,3,3,1]))  # Expected Output: 6
← Back to All Questions