Find "nth" value in BST (C)

Question

I have no idea how to go about this problem.

returns pointer to NAME_VAL pair which is the nth entry in the sorted sequence.

if i=1, you return the min entry

if i=n, you return the max entry

if n=n/2 you return the median entry (or close)

if(i < 1 || i > n) return NULL;

The runtime has to be O(log n)

Can someone point me in the right direction on the basic idea of tackling this problem? Thank you!

My structures:

typedef struct name_val 
{
    char *name;
    double value;
}NAME_VAL;

typedef struct node
{
    NAME_VAL *nV;
    struct node *left;
    struct node *right;
}NODE;

Answer 1

If the tree is perfectly balanced (with any necessary imbalance limited to the end of the sequence), you can do this by using the bit pattern for n's binary representation to guide the walk down the nodes. Since you're only asking for general guidance, I'll leave it at that rather than provide code.

If the tree is not perfectly balanced, you have to perform an O(n) depth first walk. Or add an index (which has its own cost of maintenance).