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.

#include<bits/stdc++.h>

using namespace std;

string add(string a,string b){
    string c = "";
    a = string(b.length()-a.length(),'0') + a;
    //cout<<"a = "<<a<<"b = "<<b<<"\n";
    int carry = 0;
    for(int i=b.length()-1;i>=0;--i){
        int x = a[i]-'0',y = b[i]-'0';
        int z = x+y+carry;
        c = to_string(z%10) + c;
        carry = z/10;
    }
   if(carry){
       c = to_string(carry) + c;
   }
   return c;
}

int main(){
    vector<int >cache = {1};
    string a = "1",b = "1";
    int index = 2,prev = 1;
    while(cache.size() <= 5000){
        index++;
        string c = add(a,b);
        a = b;
        b = c;
      //  cout<<c<<"\n";

        int curr = c.length();
        if(curr > prev){
            cache.push_back(index);
        }
        prev = curr;
    }
    
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<cache[n-1]<<"\n";
    }
    return 0;
}

I want to replace all the ? in range l to r with 'A' 1. first i am using function but it not working means not replacing the ? 2. second i am using for loop instead the function inside the main function and it is working correct .I am not able to understand why this happen.

all the suitable information are given in below code using comments.

Thanks.

Your text to link here...