Same BSTs

• Time : O(n^2)
• Space : O(1)

#include <vector>

using namespace std;


int smaller(vector<int>& A, int p, int minVal) {
    for(int i = p + 1; i < A.size(); i++) {
        if(minVal <= A[i] and A[i] < A[p])
            return i;
    }
    return -1;
}

int biggerOrEqual(vector<int>& A, int p, int maxVal) {
    for(int i = p + 1; i < A.size(); i++) {
        if(A[p] <= A[i] and A[i] < maxVal)
            return i;
    }
    return -1;
}

bool helper(vector<int>& A, vector<int>& B, int u, int v, int mi, int ma) {
    if(u == -1 and v == -1) return true;
    if(u == -1 or v == -1) return false;
    if(A[u] != B[v]) return false;
    int aSmall = smaller(A, u, mi), bSmall = smaller(B, v, mi);
    int aBigEq = biggerOrEqual(A, u, ma), bBigEq = biggerOrEqual(B, v, ma);
    return helper(A,B,aSmall,bSmall,mi,A[u]) && helper(A,B,aBigEq,bBigEq,A[u],ma);
}

bool sameBsts(vector<int> arrayOne, vector<int> arrayTwo) {
    if(arrayOne.size() != arrayTwo.size()) return false;
    return helper(arrayOne, arrayTwo, 0, 0, INT_MIN, INT_MAX);
}