Can anyone help not albe to find where code fails.Did almost same as editorialist @likecs.
link-CodeChef: Practical coding for everyone
@atharva_sarage, did you consider the case that the tree may not be perfectly balanced?
ie) left child = leaf and right a tree or vice versa. The condition still needs to be satisfied even if one side is a tree.
Can someone please explain setter’s solution? I am not able to understand the meaning of statement :
if (kol[p] != mx[p] - mn[p] + 1) ok = false;
TIA.
Hey, I still couldn’t understand the problem statement. How the strings are LL,RL,RR and how the input is converted to a binary tree. Can anyone please explain it properly, that would be really helpful !
The question is interesting 
@likecs In question the constraints has N>=2 but if N=2 then its impossible to build the tree because in question there is mentioned that “non-leaf: has exactly two sons — a left son and a right son”,for root is doesn’t satisfy, am i right to point it out?
Still its a interesting question
Read about vectors. Refer to geeeksforgeeks for BFS and DFS implementations.
Please convert this input into tree
5
3 5
-1 2
2 4
-1 3
-1 1
1 is the root.each line gives 2 children l and r or l=-1 means it’s a leaf.
So 1st line 3,5. so node 3,5 are children of 1. 2nd line is -1,2. so 2nd node is a leaf with value 2. 3 line is 2,4. so 3rd node has chilren 2,4 and so on.
got it thank you!
Try debugging your code for some test cases. Take this one-
Input
1
3
2 3
-1 5
-1 7
Your Output
-1
Correct Output
0 //All leaves already sorted.
Find few more test cases like that and debug using them.
1 Like
Thanks for looking into the code. But the input that you give is invalid according to constraints as it is given in contraints for any child r is less than equal to number of leafs. So in this case L =2
So only possible values for childs is 1 and 2 not 5 and 7.
Oh…lol xD. I didnt use that constraint anywhere in my solution, so kind of missed that.
@ruddradev … I Was not able to implement it in contest but now if you are still stuck you can see my solution. It’s implemented exactly as stated in editorial.
1 Like
Just look at possible variable in your code. And check this test case-
Input
2
7
2 3
4 5
6 7
-1 1
-1 4
-1 3
-1 2
5
3 5
-1 2
2 4
-1 3
-1 1
Your Output
-1
-1
Expected Output
-1
1
1 Like
Thanks @vijju123, It was a silly mistake, I didn’t reset the boolean flag for every test case which i used to check if the solution is possible or not.
Your approach is Ok, but the time complexity is wrong. It should be O(N) as there is no restriction that the binary tree is balanced. It can be skewed as well. For another easy approach, you can refer to my solution. The idea is that the number which doesn’t occur in the input is the root of the tree (The proof is easy and left as an exercise).
Can you explain what part is not clear?
@tamiliit : Thank you so much for pointing me in the right direction. I was swapping the wrong values, I had to swap the two intervals, so the start and end would become lr and rl instead of rr and ll. It was really silly of me but since you went through my code and suggested to me exactly what was needed, I got it right. Thanks again. good night.
1 Like
@rj25, For correct implementation of top-down approach, an initial traversal of the tree to calculate minimum and maximum in subtree is required which is essentially a bottom-up approach. A top-down approach can then be applied later as swaps are independent at each level.
1 Like