Nth element in Binary Search Tree using C++

Question

I am trying to find N-th element in BST using in-order traversal. I have inserted these nodes into my BST: 5, 2, 6, 7, 3, 1. When I am looking for third element it gives me another node.

Here is my code for n-th element in BST(in-order traversal):

template <class Comparable>
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>::
NthElement(BinaryNode<Comparable> *t, int *nodesVisited, int n) const
{
    //BinaryNode<Comparable>*  temp  = new BinaryNode<Comparable>();


    if(t !=NULL)
    {
        if (*nodesVisited == n)
        {
            return t;
        }else
        {
            cout << "going left \n";
            NthElement(t->left, nodesVisited, n);


            cout << "visited element= " << t->element << " nodes= " << *nodesVisited <<endl;
            cout << "going right \n";
            if (*nodesVisited < n)
            {               
                (*nodesVisited)++;
                NthElement(t->right, nodesVisited, n);
            }
            else if(*nodesVisited == n)
            {
                return t;
            }
        }
    }
}

This is a Node:

template <class Comparable>
class BinaryNode
{
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;
    int m_size;

    BinaryNode(const Comparable & theElement = -1, BinaryNode *lt = NULL, BinaryNode *rt = NULL, int size = -1)
        : element(theElement), left(lt), right(rt), m_size(size)  { }
    friend class AugmentedBinarySearchTree<Comparable>;
    friend class BinarySearchTree<Comparable>;

};

It gives me this result:

going left 
going left 
going left 
visited element= 1 nodes= 1
going right 
visited element= 2 nodes= 2
going right 
visited element= 5 nodes= 3
going right 
3 nth element 5

Answer 1

I think the below would be a simpler methodology:

node* findNodeN(node* head, int* nodesVisited, int n) {
    if (head->lt) {
        node* temp = findNodeN(head->lt, nodesVisited, n);
        if (temp) return temp;
    }
    if (*nodesVisited == n) return head;
    ++(*nodesVisited);
    if (head->rt) {
        node* temp = findNodeN(head->rt, nodesVisited, n);
        if (temp) return temp;
    }
    return nullptr;
}

Answer 2

You're ignoring an important part of the problem. You must have a way to stop in the middle of a recursive search to return the result. There are at least two ways to approach this. You can return a "failed" value (like NULL) and test for it to determine that the search hasn't yet succeeded, so keep going. Or you can just proceed as usual and throw an exception to unwind the recursion in one step. Here's the first method:

template <class Comparable>
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>::
    NthElement(BinaryNode<Comparable> *root, int *nodesVisited, int n) const
{
  if (!root) return NULL;
  BinaryNode<Comparable> *left = NthElement(root->left, nodesVisited, n);
  if (left) return left;  // Node found in left subtree. Stop searching.
  if (++(*nodesVisited) >= n) return root; // Count and skip right subtree if found.
  return NthElement(root->right, nodesVisited, n);
}