Find level of each element in BST

1

Given an array of N elements. Construct the BST , in the order as the elements are in the array and find the level of each element in BST.
Root node is at level 1.
Constraints:-
1<=N<=10^5
1<=A[i]<=10^6
All A[i] are distinct
Example:-
A = {15,6,2,9,10,13, 7}
Output:-
1 2 3 3 4 5 4

I tried constructing the BST. But found out that the worst case would end upto O(N^2) for sorted or almost sorted array.So, I got TLE.
Someone please help!

2 Likes
2

Let D[i] be the depth of the node with the number A[i] written on it. We will calculate D[i] for i=1, 2, \dots, n in that order. For a particular i, find i_1, i_2 such that i_1, i_2 < i and A[i_1] is the biggest number smaller than A[i] and A[i_2] is the smallest number greater than A[i]. We can find such an indexes on some \texttt{std::set}. Then D[i] = \max(D[i_1], D[i_2]) + 1.

4 Likes
3

Thank you that was really helpful.

4

@l_returns see this and plz code it…

5

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 upper_bound and 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.

Edit-
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.

1 Like
6

I thought of this after the contest was over :confused:

1 Like
7

I am not l_returns, but this works, at least for the sample test case provided in the question- :slight_smile:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n; 
    cin >> n;
    
    map<pair<ll, ll>, int> mp;
    set<ll> st;
    int res[n];
    
    mp[{INT_MIN - 1, INT_MAX + 1}] = 0;
    st.insert(INT_MIN - 1);
    st.insert(INT_MAX + 1);
    
    for(int i = 0; i < n; ++i) {
        ll num;
        cin >> num;
        
        ll lower = *(--st.lower_bound(num));
        ll upper = *st.upper_bound(num);
        
        st.insert(num);
        mp[{lower, num}] = mp[{num, upper}] = res[i] = mp[{lower, upper}] + 1;
    }
    
    for(auto i : res)
        cout << i << " ";
}