一道面试题 利用构建BST的过程构建数组

AMAZON Interview Question:

You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}

Time complexity : O(nlogn)
use of extra space allowed.

解：首先想到的是最直接的方法，
    for(i=0;i        for(j=i+1;j            if(ar[i] >= ar[j])
                ar_low[i]++;

   但这个方法的复杂度为O(n^2)。

   若需满足算法复杂度O(nlogn)的要求，可以使用二叉查找树，从ar数组的最后一个元素开始，逐步将ar数组元素插入到二叉查找树中，插入的过程中，即可完成对ar_low数组的赋值，由于构建二叉查找树的复杂度为O(nlogn)， 整个过程的算法复杂的也为O(nlogn)。
二叉查找树构建 平均算法复杂度为O(nlogn),但最坏算法复杂度为O(n^2)。

这里先用二叉查找树实现如下：
struct BSTnode
{
    int key;
    int index;
    struct BSTnode *left;
    struct BSTnode *right;
    struct BSTnode *parent;
};

struct BSTnode * BSTinsert(struct BSTnode *root,struct BSTnode *node)
{
    struct BSTnode *pointer = root;
    struct BSTnode *back =    NULL;

    while(pointer != NULL)
    {
        back = pointer;
        if(node->key >= pointer->key)
            pointer = pointer->left;
        else
            pointer = pointer->right;
    }

    node->parent = back;

    if(back ==  NULL)
        root = node;
    else if(node->key >= back->key)
        back->left = node;
    else
        back->right = node;

    return root;
}

void Free(struct BSTnode *root)
{
    if(root != NULL)
    {
        Free(root->left);
        Free(root->right);
        free(root);
    }
   
}
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    int n = 7;
    int ar[] = {1,3,2,4,5,4,2};
    int *ar_low = (int *)calloc(n,sizeof(int));
    struct BSTnode *root = NULL;

    for(int i=n-1;i>=0;i--)
    {
        struct BSTnode *node = (struct BSTnode *)malloc(sizeof(struct BSTnode));
        node->key = ar[i];
        node->index = i;
        node->left = node->right = NULL;
        node->parent = NULL;
        root = BSTinsert(root,node);
        if(node->parent!=NULL)
        {
            if(node->parent->left == node)
                ar_low[i] = ar_low[node->parent->index] + 1;
            else
                ar_low[i] = ar_low[node->parent->index];
        }else
            ar_low[i] = 0;

    }

    for(int i=0;i        printf("%d ",ar_low[i]);
    printf("\n");

    free(ar_low);
    Free(root);

}