Yes it is. (If I understood the problem right)

In nodes you should keep how many nodes are there already in the subtree. Lets call it size of the subtree. (size of parent is size of left tree + size of right tree)

Recursive Query goes like:

When you see your left subtree's size is > k, you check the left subtree, else you look in the right subtree for a tree of size k — size of left subtree

Suppose you are given numbers from 0 to n — 1, now you've to find the kTh element. (If the numbers are enough large, I'd map them with relative small numbers.)

In the interval tree, every node will contain how many elements are there in it's range. Now you can use binary search to find the answer. Here is the sample code:

struct node {
    int left, right; // for range, [left, right];
    int count; // number of element in the range

    node *left_child, *right_child;
}

int binary_search (int kTh) {
    node *x = root;
    if (x -> count < kTh) return INF;

    while (true) {
        if (x -> left == x -> right) return x -> left; // leaf node
        if (x -> left_child -> count < kTh) {
            kTh -= x -> left_child -> count;
            x = x -> right_child;
        } else x = x -> left_child;
    }
}

UPD: There is a simpler version of this interval tree. I know it by the name of 'misof tree'. Here is a sample code. I've changed the original code though but the basic idea is same.

I have a N*sqrt(N)*log(sqrt(N)) solution. And it got accepted. How is this possible?