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.

CodePudding user response：

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);
}

CodePudding user response：

this code is beyond my knowledge, but maybe count needs to go before recursing? Because you are calling the recursion without increasing the count in your code. Example:

if (count <= N) {
    count  ;
    findNthElement(N, tree->left);

CodePudding user response：

You dont have to define count as static at all, you can directly increment parameter and call recursively until N == count. Whenever you call the function, even recursively, then a new count variable will be created in the memory stack.

TreeNode* findNthElement(int N, TreeNode* tree, int count) {
    TreeNode * nthTree = NULL;
    if(tree == NULL) 
        return NULL;

    //Found the Nth element
    if (count == N){
       return tree;
    }
    
    //Not using   count just for clarity
    //First it will check left subtree, if its Nth then return it else go right
    nthTree = findNthElement(N, tree->left, count 1); //Recursive call for left node

    //Recursive call for right node
    return (nthTree == NULL) ? findNthElement(N, tree->right, count 1) : nthTree; 
     
}

CodePudding user response：

in order to find the nth smallest element in BST, you can apply logic as follows:

using System.Collections.Generic;
public int smallElement(int k)
{
    Node<T> node = Root;
    int count = k;
    int sizeOfSubTree =0;
    
    while (node != null)
    {
        sizeOfSubTree = node.SizeOfLeftSubTree();
        if(sizeOfSubTree  1 == count)
        {
            return node.Value;
        }
        else if(sizeOfSubTree  1 < count)
        {
            node=node.Right;
            count -= sizeOfSubTree  1 ;
            
        }
        else
        {
            
            node = node.Right;
        }
        
    }
    return -1;
    
    
}

you can also check following resources to get help:

in-order traversal to find nth node

Find k’th smallest node in a Binary Search Tree (BST)

hope this might help you.