CareerCup

Node * KthSmallest(Node *n, int k)
{
    int leftCount;
    if (n->pLeft == NULL)
        leftCount = 0;
    else
        leftCount = n->pLeft->count;

    if (leftCount + 1 == k) return n;
    if (leftCount + 1 < k) return KthSmallest(n->pRight, k - 1 - leftCount);
    return KthSmallest(n->pLeft, k);
}

In main() call

Node *pSolution = KthSmallest(pRoot, inOrderNumber);

There is really no point for recursion here. I think that using recursion at these places is actually not a good practice. Though on a similar lines using iteration, this code looks more efficient to me:

Nodeptr nthInInorder(Nodeptr root, int x){
 Nodeptr curr = root;
 int countedIn = 0, leftchildren = 0, currIn=0;

 while(curr!=NULL){
  if(curr->left == NULL)
   leftchildren = 0;
  else
   leftchildren = (curr->left)->data + 1;

  currIn = countedIn + leftchildren + 1;

  if(currIn == x)
   return curr;
  else if(currIn > x)
   curr = curr->left;
  else if(currIn < x)
   { countedIn = currIn + 1;
     curr = curr->right;
   }
  }
  return NULL;
 }