Problem Statement : An array of unique elements is given and we make to BST from this array. These values must be appear in the same order as they appear in array. we need to find the level of each values in BST.

Example :
                 array  : 15 6 2 10 9 7 13
                 Levels : 1 2 3 3 4 5 4

My approach : 1. first make a BST using insertion each element into BST so complexity O(N^2). 2. apply level order traversing and store level of each node into map. O(N). 3. find final result array using map. O(N)

can anyone suggest a better approach. Note : we cannot apply sorting to array for making BST in O(N) because the values must be appear in the same order as they appear in array. So if we apply first sorting array and than make BST than it will change order.