Is there any linear solution to this problem? I have implemented an O(NlogN) one.

Let me tell you the  way I've solved it. We just pick our last vertex (number) as a root and try to divide another part into 2 subtrees. In order to do this we find a border between those 2 parts, so that all numbers in the first part are less than our root and vice-versa for second part. The latter can be easily implemented using binary search. And then we just do all the same from the very beginning with both parts recursively. It's obvious that the only time-consuming part is binary search, which takes O(logN) time in the worst case. Therefore the complexity of this algorithm is O(NlogN).

Here you are! I have user bst think that time is O(n) good luck!

[code deleted]

Edited by moderator 20.06.2020 16:13

My algorithm is not optimal.. It's like, I start from last vertex and add in BST. after I finish this, I print this tree according to problem statement.  It's NlogN algorithm and I still have TLE on 9 test.. N is at most 3 000 and why isn't it enough?? :/

Because the algorithm is not optimal. If the tree is unbalanced then your solution will go to O(N ^ 2). See it yourself with a sorted input.