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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make Costs of Paths Equal in a Binary Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • The tree is a perfect binary tree, meaning all levels are fully filled.
  • Each leaf node can be reached through a unique path from the root.
  • The goal is to make the total costs of all root-to-leaf paths equal by only incrementing costs.
  • The maximum cost among all leaf nodes determines the target cost for all paths.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a depth-first search (DFS) approach to traverse the binary tree. We will calculate the costs of all paths from the root to each leaf node. The algorithm will keep track of the maximum path cost encountered. Once we have the maximum path cost, we can calculate the number of increments needed to make all paths equal to this maximum cost.

  1. Initialize a variable to hold the maximum path cost.
  2. Perform a DFS traversal from the root node, summing the costs along the path.
  3. When a leaf node is reached, compare the current path cost with the maximum path cost and update if necessary.
  4. Calculate the total increments needed by summing the differences between the maximum path cost and each leaf's current path cost.

Code Solutions

def min_increments(n, cost):
    def dfs(node, current_cost):
        if node > n:
            return
        current_cost += cost[node - 1]
        if node * 2 > n:  # Leaf node
            leaf_costs.append(current_cost)
            return
        dfs(node * 2, current_cost)  # Left child
        dfs(node * 2 + 1, current_cost)  # Right child

    leaf_costs = []
    dfs(1, 0)  # Start DFS from the root (node 1)
    
    max_cost = max(leaf_costs)
    increments = sum(max_cost - leaf_cost for leaf_cost in leaf_costs)
    
    return increments
← Back to All Questions