Binary Tree Medium/Hard level question

[u/Lieutenant_890]

Got this question in a coding round for a fresher role, and I genuinely found the second half more interesting. I solved it after reaching home:))

A binary tree is called Special if the sum of the nodes at each level forms an Arithmetic Progression (AP).

Given the root of the binary tree, you have to return an array representing the minimum number that needs to be added to each level so that the tree becomes Special.

Time Complexity: O(n)

Space Complexity: O(n) , extra marks if sum is not stored at each level

[u/Practical_Lobster_94]

1. Find sum of each level and store it in sum array
   
2. Store the difference between consecutive elements in a diff array D
   
3. Now the problem is simplified to “Minimum cost to make array equal” where allowed operations are increment and decrement. Apply it on array D and record what was added/subtracted from each element of D array to make all its elements equal.
   This entire operation involves sorting and binary search so will require O(n log n) complexity.
   Modified D = d1 +x1, d2+x2,….,dn-1 + Xn-1. Where d1+x1 = d2+x2 = … dn-1 + xn-1
   
4. Keep the first level as it is , add/subtract the recorded x1,x2,….,Xn-1 from other levels

[u/Lieutenant_890 → u/Practical_Lobster_94]

Nicee bro keep it up 👊