6B2018

/*
    Złożoność obliczeniowa: O(n)
    Złożoność pamięciowa: O(n)
*/
struct wezel {
    int w;
    struct wezel *l;
    struct wezel *r;
}
typedef struct wezel Twezel;

/* Zlicza ile węzłów ma drzewo */
int ile(Twezel* d)
{
    if(d == NULL)
        return 0;
    else
        return (ile(d->l) + ile(d->r) + 1);
}
/*
    Przechodzi drzewo w kolejności infiksowej lewo prawo (LVR) wpisując elementy do tablicy
    W wyniku dostajemy tablicę posortowanych wartości
*/
void tablica(Twezel *d, int *i, int A[])
{
    if (d != NULL) {
        tablica(d->l, i, A);
        A[i] = d->w;
        *i += 1;
        tablica(d->l, i, A);
    }
}

int pary(Twezel *d, int k)
{
    int n = ile(d);
    int *A = malloc(n * sizeof(int));
    int *index;
    *index = 0;

    tablica(d, index, A);

    /*
        Dla danego i znajduje pierwsze j takie, że A[i] - A[j] < k
        Wtedy liczba dobrych par z tym i to (n - j)
    */
    int licznik = 0;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && (A[i] - A[j]) >= k)
            i++;
        licznik += (n - j);
    }
    return licznik;
}