Why does sorting the array give incorrect result?

#1

So, basically, in the question, Build BST from a sorted array of n intergers, I forgot to read that the array is sorted. Hence I sorted the array using the sort function and then solved the question. Only 1 Testcase passed

However, later I noticed that the array is already sorted in input, hence no need to sort it again. So I uncommented that line and guess what? All testcases passed

It would be great if anyone explained this miracle to me !

The code is over here : https://ide.codingblocks.com/s/312699

Refer to the uncommented line on Line No 55

Also, the same question using redundant sorting, on GFG passed all the test cases. So is there something wrong with this question’s test case?

#2

hi @devpratik it is not mentioned that the data will be sorted, the sample input just happens to be sorted, but there might be other test cases where data is not sorted.

#3

I think you might have misunderstood my question.

Firstly, the input is indeed sorted. The first line of the question mentions that
You are given a sorted data of n integers. You have to form a balanced Binary Search Tree and then print preorder traversal of the tree.

Secondly, let’s suppose the data isn’t sorted, and the problem statement has a typo. Then ideally the we have to sort the array, as the question clearly states to form a “Balanced” binary tree. If we don’t sort the array, we might end up with a skewed tree.
So, in that case, the sorted array answer should pass all test cases, but the unsorted one should fail. However, the opposite of that is happening. The unsorted input passes all the test cases, the sorted one fails.

#4

@devpratik can you give me the link of both the codes? which failed and passed

#5

Sure, the code which failed can be found here : https://ide.codingblocks.com/s/312701
The code which passed has only one change from the above code, there the line number 55 is commented out.

You could try using the same code given above for input both the times and see the difference when line 55 is uncommented, and when it is commented

#6

@devpratik i checked the test cases, input is not given in sorted order for all the test cases.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

@devpratik same miracle happened with me also. If you got the proper explanation for this, can you please tell me? It’ ll be a great help.