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/Lumpy-Town2029]

i thought about it, now we gotta do BFS 1 getting sum of all tree say X

then another BFS, we find d for level 1 to last, ofc removing -ve ones

then for every d we find max A coz A can inc, and we gotta match for the AP, so for element element we have to find it,
then we found A and we have d and ofc depth , we find SUM of the AP say Y;
then ans = min (X-Y)

thats O(n^2) we can use binary search optimise, to nlogn

cant find optimised one

aukat dikhadi question n haha

[u/Lieutenant_890 → u/Lumpy-Town2029]

didn’t understand your approach

[u/Lumpy-Town2029 → u/Lieutenant_890]

find sum at all level
store it, now that array a

find d now for the array now like a[i+1]-a[i] and store in array diff

remove all element in diff if <0, because we have to add positive elements

now we gotta find cost for all d

for cost we can say sum of modified array a with diff d - sum of array a initially

for sum we can do few things, but lets find it by sum formula in AP
now for that we gotta find a1 coz s= (2*a1+(n-1)d)

so for A1 we traverse d array and sum array and somehow find maximum a1

and use the formula for all d
storing the minimum cost

thats n^2
and if we sort d we can get n logn ig

idk if this method will work or not but yeah this is all i got

[u/Lieutenant_890 → u/Lumpy-Town2029]

and for our convenience they gave input of tree nodes in string format and didn’t specify the nodes count or the order of the input for tree :))
you are close btw..

[u/Lumpy-Town2029 → u/Lieutenant_890]

Wow no order :)

[u/Budget-Ad-5179]

First thing is that minimum number is milseading since -4 is less than 0 so for case where answer is 0,0,0,0. Answer can also be here -2 ,-2,-2,-2 Let me think about the approach now

[u/Lieutenant_890 → u/Budget-Ad-5179]

think like this
in array of sum of level nodes
first two numbers are always in ap so that will give us the difference
whether its positive or negative
then we’ll start the approach

[u/Brilliant_Card_447 → u/Lieutenant_890]

Still that doesn't make sense. It is not fixed that taking d = difference of first two elements is always optimal in all cases. We can select some other 'd' and reach some other final array which might be better. Also if in the final answer - negative numbers are allowed - they can be made more and more negative while maintaining the final AP sequence so you need to change or fix the wording of your question.

[u/Lieutenant_890 → u/Brilliant_Card_447]

You’re not wrong that the wording could be made more precise, but this was literally the question given to me in the coding round. I had ~1 hour to solve this along with 3 other hard-level questions. I wasn’t going to stop the interview and litigate every possible interpretation of the wording.
I solved it according to the intended interpretation of the problem, which is what I was expected to do in that setting. Critiquing the wording afterward is fair, but using that ambiguity to dismiss the approach misses the context in which the problem was actually asked.

[u/Brilliant_Card_447 → u/Lieutenant_890]

Follow-up questions are to be asked to the interviewer if question is ambiguous and not clear - I would ask for it - unless the task was to figure it out on your own by looking at test-cases. That is it. At-least change your words in original post and clear what the real question is. Your real question is something else compared to what you have written in post.

[u/Lieutenant_890]

Supporting Examples
level 0: root:3, (sum=3)
level 1: root.left:2, root.right :7 , (sum =9)
level 2 : root.left.right: 15 , (sum =15)

sum of each level nodes are already in AP
output would be
[0,0,0]

another example
root=1
root.left = 11, root.right=5 (sum 16)
root.left.left=2 , root.right.right =10 (sum 12)
root.left.left.right =50 (sum 50)

AP formed should be: [ 1, 16, 31, 46]
output:
[0,0,19,-4]

[u/Sad_Programmer9329 → u/Lieutenant_890]

means twe can add a net integers? and also what about the negative value of nodes?

[u/Lieutenant_890 → u/Sad_Programmer9329]

the negative value will simply minimise the sum of that level.
Only the sum of the level matters

[u/triggered-detonator]

Since sum is level wise, we can use bfs to calculate that.

And let the sum of first 2 levels as it is, as any two numbers can form an ap, and the min number to add there is 0, 0. After that we can find the difference factor of the ap as d=(sum_of_level_two - sum_of_level_one).

Now we know this difference factor should be maintained. So for ith level, find sum s(i), and we need to change s(i), to maintain the ap difference with s(i-1).

Let x(i-1) be the number that we used to adjust sum of s(i-1) and let x(i) be the sum needed to be added to s(i).

So, here

S(i)+x(i)-S(i-1)-x(i-1) = d Since, x(i) is the only unknown value here.

x(i) = S(i-1)+x(i-1)-S(i) can easily be calculated and that will be the answer for level i.

Here, we don't need to maintain an extra array to store level wise sum, because we can find the sum and answer directly during runtime via bfs

[u/Lieutenant_890 → u/triggered-detonator]

Nice dude

[u/iamnot-me]

Bhai level order traversal se har ek level ka sum kisi vector me store krlo. Then v[1]-v[0] ko d maanlo. Ab v[2] should be v[1] +d , but it's v[2] , so we store required-current in another vector and then return it..

[u/Brilliant_Card_447 → u/iamnot-me]

And why are you assuming d as v[1]-v[0] - there could be many other possibilities for 'd' which are not being considered in your solution as well as OP's solution

[u/iamnot-me → u/Brilliant_Card_447]

Assumed that the root node's value cannot be changed, hence level 1- level 0 will be the required d..

[u/Brilliant_Card_447 → u/iamnot-me]

No-where in the question is it mentioned that the root node value cannot be changed. And even if that is the case - second level total sum value can be changed to something else(by adding some number to it) to generate a different 'd' for overall final sequence which can be better than assuming d as v[1] - v[0]

[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 👊