2673. Make Costs of Paths Equal in a Binary Tree


Problem Description

The problem provides us with a perfect binary tree with nodes numbered sequentially from 1 to n. In this tree, each non-leaf node has exactly two children: the left child is 2 * i and the right child is 2 * i + 1, where i is the node number of the parent. A cost array of size n tells us the cost associated with each node, and the index of the cost array is 0-indexed, meaning cost[i] corresponds to the cost of node i + 1.

The objective is to ensure that the total cost from root to any leaf is the same for all paths. To achieve this, you can increment the cost of any node by 1 as many times as needed. The task is to find out the minimum number of increments required to make all root-to-leaf path costs equal.

Key concepts to understand:

  • Perfect binary tree: A binary tree where all non-leaf nodes have two children and all leaves are at the same level.
  • Path cost: The sum of costs of all nodes from the root to a leaf node.
  • Minimum increments: The least number of single-unit increments to the nodes' costs to equalize the path costs.

Intuition

The intuition behind this problem is to ensure that for any two sibling nodes, the paths from these nodes to their respective leaves have the same cost. If one path has a higher cost to a leaf than the other, we will have to increment the cost of nodes on the cheaper path.

This condition must hold true at every parent node in the tree, as ensuring this locally at every node will result in equal path costs for all leaf nodes.

Here's the thought process for arriving at the solution:

  1. Perform a depth-first search (DFS) from the root to the leaves. This will allow us to calculate the costs from a node to its leaves recursively.
  2. For every node, calculate the costs for the left and right paths independently using DFS.
  3. For sibling nodes, find the difference in these costs and add this difference to a global ans variable which keeps the running total of all increments needed.
    • The smaller path cost will be increased by this difference to match the larger one.
  4. The new cost of each node will be its own cost plus the higher of its children’s path costs (after any increments to equalize them).
  5. Recursively apply this process until all leaf nodes' path costs have been handled.
  6. The ans variable will contain the sum of differences after the DFS is completed, which is the answer.

This approach works because it systematically ensures each node’s subtree contributes equally to the final path costs, adhering to the perfect binary tree's inherent symmetry, which dictates that the paths from root to leaf are balanced.

Learn more about Greedy, Tree, Dynamic Programming and Binary Tree patterns.

Solution Approach

The solution approach uses recursion, which is inherent in a depth-first search (DFS) pattern, to journey through the perfect binary tree. While this may look complex on the surface, it breaks down into a series of simple operations. Let's dissect the code and the related algorithms, data structures, or patterns used:

  1. Depth-First Search (DFS):

    • The dfs function is a recursive function that takes a node i as an argument.
    • The base case for recursion happens when the current node i does not have children, indicating a leaf node. At this point, it returns the cost of the leaf node (cost[i - 1]).
  2. Binary Tree Structure and Node Indices:

    • In a perfect binary tree, the left child of node i is at index 2 * i, and the right child is at 2 * i + 1.
    • The solution uses this formula to recursively call dfs on child nodes and calculate their path costs up to the leaves.
  3. Cost Calculation and Comparisons:

    • For a non-leaf node, recursive dfs calls are made for both left and right children.
    • The l and r variables store the maximum path costs from the current node to the leaves of the left and right subtrees, respectively.
    • We ensure both subtrees have equal contribution to the path cost by adding the difference between l and r to the global ans variable. The max(l, r) - min(l, r) operation calculates the cost needed to balance the two paths.
  4. Global State Variable:

    • The ans variable accumulates the total increments needed. It's declared as nonlocal within dfs so that its state is maintained across recursive calls without passing it as an argument.
  5. Returning Computed Costs:

    • After calculation and potentially equalizing the costs of the paths from the left and right children, dfs returns the cost of the current node (cost[i - 1]) plus the maximum of the two child path costs (max(l, r)). This ensures that the cost of this node contributes to the total path cost accurately.
  6. Initiation and Return Value:

    • The DFS traversal is initiated by calling dfs(1) from the root of the tree, which is node 1.
    • After the DFS completes, the ans variable has accumulated all the necessary increments to balance the tree's cost paths, and it is returned as the solution to the problem.

By using DFS in this manner, the solution leverages the recursive nature of trees to perform calculations at each node, ensuring that each node's contribution to the path cost is accounted for precisely in a bottom-up fashion. This results in the entire tree having equal-cost paths from the root to each leaf, with the minimum number of increments needed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's use a simple perfect binary tree with four nodes, which looks like this:

       1(0)
      /   \
   2(1)   3(2)
   / \    / \
 4(0) 5(1) 6(0) 7(0)

Here, the numbers inside the parentheses denote the initial cost associated with each node. The numbering of the nodes is sequential and represents the level-order traversal of the tree. For example, the root is node 1 with a cost of 0, left child of the root is node 2 with a cost of 1, and so on.

Let's walk through the process following the DFS solution approach:

  1. Start the DFS traversal from the root, which is node 1.
  2. For node 1, call the dfs function recursively on its left and right children (nodes 2 and 3).
  3. For node 2, it is not a leaf but has children 4 and 5:
    • Call dfs on node 4 (leaf node), which returns its cost, 0.
    • Call dfs on node 5 (leaf node), which returns its cost, 1.
    • The left and right child costs (l and r) of node 2 are 0 and 1, respectively.
    • To balance this, we need to make 1 single increment to node 4, so the cost becomes 1 like its sibling node 5.
    • Update ans to 1 (number of increments needed so far).
    • The updated cost at node 2 will be its own cost 1 plus the maximum of its children's costs, which is 1, so the total becomes 2.
  4. Similarly, for node 3:
    • It also has two children, nodes 6 and 7, both of which are leaf nodes with a cost of 0.
    • After calling dfs on nodes 6 and 7, we get the costs 0 for both, and no increments are needed since they are already equal.
    • The updated cost at node 3 will be its own cost 2 plus the maximum of its children's costs, which is 0, so the total becomes 2.
  5. Back at the root node 1, we now have the costs from node 2 and node 3, both equal to 2 (after the necessary increment in step 3).
    • Here, no additional increment is needed since the path costs are already equal.
  6. By the end of DFS, ans equals 1, which means we only needed to perform 1 increment to achieve equal costs from the root to all leaves.

In this example, the minimum number of increments is 1. We only needed to increment the cost of node 4 to equalize the path costs from the root to every leaf.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minIncrements(self, n: int, costs: List[int]) -> int:
5        # Define a depth-first search function to compute the minimum cost increment.
6        def dfs(node_index: int) -> int:
7            # Base case: If the current node is a leaf node, return its associated cost.
8            if (node_index << 1) > n:
9                return costs[node_index - 1]
10          
11            # Recursively find the min increment cost of the left and right children.
12            left_cost = dfs(node_index << 1)
13            right_cost = dfs(node_index << 1 | 1)
14          
15            # Update the total increments by adding the difference between the children's costs.
16            nonlocal total_increments
17            total_increments += abs(left_cost - right_cost)
18          
19            # Return the cost of this node plus the maximum cost of its children.
20            return costs[node_index - 1] + max(left_cost, right_cost)
21
22        # Initialize the total increments variable.
23        total_increments = 0
24      
25        # Start the depth-first search from the root node (index 1).
26        dfs(1)
27      
28        # Return the total minimum increments to balance the binary tree.
29        return total_increments
30
31# Example usage:
32# solution = Solution()
33# min_increments_result = solution.minIncrements(n, cost_list)
34# print(min_increments_result)
35
1class Solution {
2    // Class variables to hold the input array and its size, and to accumulate the answer.
3    private int[] nodeCosts;
4    private int treeSize;
5    private int totalIncrements;
6
7    // Method to initiate the process and return the final answer.
8    public int minIncrements(int treeSize, int[] nodeCosts) {
9        this.treeSize = treeSize;
10        this.nodeCosts = nodeCosts;
11        totalIncrements = 0; // Initializing the total increments to 0.
12
13        // Start the depth-first search from the root node, which is index 1 in this 1-indexed array.
14        dfs(1);
15
16        // Return the accumulated total increments needed for the tree.
17        return totalIncrements;
18    }
19
20    // Recursive depth-first search to calculate the increments required.
21    private int dfs(int index) {
22        // Base case: If the node is a leaf, return its cost.
23        if ((index << 1) > treeSize) {
24            return nodeCosts[index - 1];
25        }
26      
27        // Calculate the required increments for the left child.
28        int left = dfs(index << 1);
29        // Calculate the required increments for the right child.
30        int right = dfs(index << 1 | 1);
31
32        // Increment the total by the difference between the costs of left and right subtrees.
33        totalIncrements += Math.abs(left - right);
34
35        // Return the cost of this node plus the maximum of its children's cost.
36        // This ensures that we are increasing the smaller child's cost to match the larger one's.
37        return nodeCosts[index - 1] + Math.max(left, right);
38    }
39}
40
1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7    // Method that computes the minimum increments needed for the binary tree
8    // represented by 'cost', given the number of nodes 'n'.
9    int minIncrements(int n, vector<int>& cost) {
10        // Initialize the answer to 0
11        int totalIncrements = 0;
12
13        // Define a lambda function for depth-first search computation.
14        // This lambda function is recursive and calculates the minimum increments
15        // for the subtree rooted at node 'i'.
16        function<int(int)> dfs = [&](int i) -> int {
17            // If the current index 'i' has children beyond the range of the tree, return its cost.
18            if ((i << 1) > n) {
19                return cost[i - 1];
20            }
21            // Recursively compute the cost for the left child.
22            int leftCost = dfs(i << 1);
23            // Recursively compute the cost for the right child.
24            int rightCost = dfs(i << 1 | 1);
25            // Increment the answer by the difference between the left and right costs.
26            totalIncrements += max(leftCost, rightCost) - min(leftCost, rightCost);
27            // Return the cost for the current node which is the sum of its own cost
28            // and the maximum of its children's costs.
29            return cost[i - 1] + max(leftCost, rightCost);
30        };
31
32        // Start the DFS from the root node, which is indexed as 1.
33        dfs(1);
34        // Return the total number of increments computed.
35        return totalIncrements;
36    }
37};
38
1function minIncrements(nodeCount: number, nodeCosts: number[]): number {
2    // Initialize the variable to store the total number of increments required.
3    let totalIncrements = 0;
4
5    // Define a Depth-First Search function that calculates the cost to balance the tree starting from a given node index.
6    const dfs = (nodeIndex: number): number => {
7        // If the current node is a leaf node, return its cost.
8        if (nodeIndex * 2 > nodeCount) {
9            return nodeCosts[nodeIndex - 1];
10        }
11
12        // Recursively calculate the cost for the left and right children of the current node.
13        const leftCost = dfs(nodeIndex * 2);
14        const rightCost = dfs((nodeIndex * 2) | 1);
15
16        // Increment the total number of increments required by the difference in costs of left and right children.
17        totalIncrements += Math.abs(leftCost - rightCost);
18
19        // Return the total cost of this subtree, which is the cost of the current node plus the maximum cost of its children.
20        return nodeCosts[nodeIndex - 1] + Math.max(leftCost, rightCost);
21    };
22
23    // Start the DFS from the root node, which is at index 1.
24    dfs(1);
25
26    // Return the total number of increments required to balance the cost across the tree.
27    return totalIncrements;
28}
29

Time and Space Complexity

The given code performs a depth-first search (DFS) on a binary tree that is implicitly defined by the input value n. For every node i, the function dfs is called on 2 children if they exist: i << 1 (left child, representing 2 * i) and i << 1 | 1 (right child, representing 2 * i + 1). The tree is essentially a complete binary tree up to the level where the nodes have values less than or equal to n. At each call of dfs, it computes the maximal cost of making the subtree rooted at i balanced.

Time Complexity

Since each non-leaf node makes two recursive calls, and each recursive call works on half of the remaining nodes (binary tree property), the time complexity is determined by the number of nodes in the tree:

  • For a complete binary tree with n nodes, the number of edges is n - 1.
  • The complexity is proportional to the number of edges traversed, which is bound by O(n).

Therefore, the overall time complexity of the code is O(n), where n is the number of input nodes in the tree.

Space Complexity

The space complexity of the code is determined by two factors: the recursion call stack and the nonlocal variable ans used to accumulate results.

  • The depth of the recursive call stack for a complete binary tree is log(n) where n is the number of nodes. This is because we only go as deep as the height of the tree.
  • The variable ans does not depend on the size of the input but is a single integer used to accumulate the cost.

Thus, the space complexity is O(log(n)) reflecting the depth of the recursion call stack for a complete binary tree of n nodes.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!