Challenge
Challenge
Problem
Solutions
Submissions
Challenge Points: 20
Level: MediumYou’re given a perfect binary tree with nodes 1..n (root at 1, children of i are 2*i and 2*i+1).
cost[i] is the cost of node i+1. You may increment any node’s cost by 1 any number of times.
Return the minimum total increments needed so that every root-to-leaf path has the same sum.
Key idea (greedy bottom-up):
For each node, let S(i) be the (post-increment) path sum from node i down to any leaf in its subtree. To minimize increments, we raise the smaller child path up to the larger one.
If left sum = L, right sum = R, we must add |L−R| increments; then S(i) = cost[i] + max(L, R). Summing |L−R| over all internal nodes yields the minimum.
Input: n = 7 cost = [1,5,2,2,3,3,1]
Output: 6
Explanation:
After increments, each root-to-leaf path totals 9. One optimal plan is: - node 4 +1 - node 3 +3 - node 7 +2 Total increments = 1 + 3 + 2 = 6.
Input: n = 3 cost = [5,3,3]
Output: 0
Explanation:
Paths (1→2) and (1→3) already have equal sums (8), so no increments needed.
Input: n = 3 cost = [0,0,1]
Output: 1
Explanation:
Left path sum = 0 (1→2), right path sum = 1 (1→3). Increase the left child (node 2) by 1 (or the root by 1) to balance → total increments = 1.
Accepted:
Submission:
Report an issue
Code
You need toto run or submitYou need toto run or submit
Test Case
Test Result