This can be done in the same way you would solve the problem, ‘Find if a given tree is a BST’.
Initially, assume the range of all possible values in [-\infty, \infty]. Now, root will always be the first number. Let’s the value of root is
root-val then, all nodes to the left will have their value lie in [-\infty, root-val] and similarly all nodes their value lie in [root-val, \infty]. Now, all we have to do is to find the appropriate range for each input. Initially, map (-\infty, \infty) to 0(level). Then for each element search it’s closest smaller number and closest larger number already in the map. This can be done using
lower_bound in logarithmic time. Suppose these numbers and U_L and L_L respectively, then all you have to do is to search for the range (L_L, U_L) in the map and then the answer(the level) for the current number will be 1 + the level the range (L_L, U_L) is mapped to, we also insert to new ranges (current-val, U_L) . and (L_L, current-val) into the map and map them to the level of the current node(that we just found in the previous step).
Time Complexity - O(N * log_2(N))
Space Complexity - O(N) - two times the number of nodes.
I missed this point but I guess this should be fairly obvious. If while searching for the closest smaller number, you don’t find anything in the map(the current number is the smallest) then you should be returning -\infty for that and similarly \infty if no larger element is found.