How do I find the Nth element in a binary search tree?

Question

I have a binary search tree in C, the goal currently is to find the Nth element in the tree. I am attempting to do this recursively, however this is not paramount. I have access to the amount of nodes under any given node (inclusive).

I tried this block of code:

TreeNode* findNthElement(int N, TreeNode* tree) {
  static int count = 0;
  printf("nodeCount: %d\nN: %d\nCount: %d\n", tree->nodeCount, N, count);//debug
  //null case
  if (tree == NULL) {
    return NULL;
  }
  //recursion
  if (count <= N) {
    findNthElement(N, tree->left);
    count++;
    if (count == N) {
      count = 0;
      return tree;
    }
    findNthElement(N, tree->right);
  }
}

This is supposed to be a recursive function to complete my task but count's value is always 0 even though it is static. I have also tried initializing count outside of the function and resetting it to 0 upon success or failure but that has also not succeeded.

Answer 1

Your code ignores the node that is returned from the recursive call, so if that recursive call had found the target node, the caller is not aware of it. Moreover, after the findNthElement(N, tree->right) call, nothing is returned.

Also, you shouldn't use a static count. The counting logic can be satisfied by reducing the value that will be passed as N-argument to the recursive call.

Here is an implementation:

TreeNode* findNthElement(int n, TreeNode* tree) {
    if (tree == NULL) {
        return NULL;
    }
    int currentNum = tree->left == NULL ? 1 : tree->left->nodeCount + 1;
    return n == currentNum ? tree // Found it!
         : n <  currentNum ? findNthElement(n, tree->left) 
                           : findNthElement(n - currentNum, tree->right);
}