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:
- 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.
- For every node, calculate the costs for the left and right paths independently using DFS.
- 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.
- 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).
- Recursively apply this process until all leaf nodes' path costs have been handled.
- 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:
-
Depth-First Search (DFS):
- The
dfs
function is a recursive function that takes a nodei
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]
).
- The
-
Binary Tree Structure and Node Indices:
- In a perfect binary tree, the left child of node
i
is at index2 * i
, and the right child is at2 * i + 1
. - The solution uses this formula to recursively call
dfs
on child nodes and calculate their path costs up to the leaves.
- In a perfect binary tree, the left child of node
-
Cost Calculation and Comparisons:
- For a non-leaf node, recursive
dfs
calls are made for both left and right children. - The
l
andr
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
andr
to the globalans
variable. Themax(l, r) - min(l, r)
operation calculates the cost needed to balance the two paths.
- For a non-leaf node, recursive
-
Global State Variable:
- The
ans
variable accumulates the total increments needed. It's declared asnonlocal
withindfs
so that its state is maintained across recursive calls without passing it as an argument.
- The
-
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.
- After calculation and potentially equalizing the costs of the paths from the left and right children,
-
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.
- The DFS traversal is initiated by calling
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 EvaluatorExample 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:
- Start the DFS traversal from the root, which is node 1.
- For node 1, call the
dfs
function recursively on its left and right children (nodes 2 and 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.
- Call
- 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.
- 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.
- 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 isn - 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)
wheren
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.
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
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Don’t Miss This!