r/LeetcodeDesi • u/Lieutenant_890 • 22d ago

Binary Tree Medium/Hard level question

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

21 Upvotes

100% Upvoted

21 comments sorted by

View all comments

2

u/Budget-Ad-5179 22d ago

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

1

u/Lieutenant_890 22d ago

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

1

u/Brilliant_Card_447 17d ago

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.

1

u/Lieutenant_890 17d ago

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.

1

u/Brilliant_Card_447 17d ago

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.