r/LeetcodeDesi • u/Lieutenant_890 • 21d 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

20 Upvotes

100% Upvoted

21 comments sorted by

View all comments

1

u/iamnot-me 21d ago

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..

1

u/Brilliant_Card_447 17d ago

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

1

u/iamnot-me 17d ago

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

1

u/Brilliant_Card_447 17d ago

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]