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 4My 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.
It's from a live contest
Contest is over now. This can be done in O(n*logn). For every element of the array, find two elements, one which is just greater and one which is just smaller on the left of it. The level of that element is maximum of the levels of the two + 1