Finding the k-th element in a BST Given a Binary Search Tree, determine its k-th  element in inorder traversal.


Here's my node structure:

struct node 
{
    int elem;
    node *left, *right;


    static node* create(int elem)
    {
        node *newnode = new node;
        newnode-&gt;elem = elem;
        newnode-&gt;left = newnode-&gt;right = NULL;
        return newnode;
    }   

        // Forget freeing up memory

};


Here's my BST:

class tree
{
  private:
  node *root;

  public:
  tree(int elem)    { root = node::create(elem); }

  bool insert(int elem) 
  {
    node *newnode = node::create(elem);
    node *travnode = root;

    while(1)
    {
      if(elem &amp;lt travnode-&gt;elem) 
      {
        if(travnode-&gt; left == NULL)
    {
      travnode-&gt;left = node::create(elem);
      return true;
    }
    else travnode = travnode-&gt;left;
      } // elem &lt; travnode-&gt;elem
      else
      if(elem &gt; travnode-&gt;elem)
      {

        if(travnode-&gt;right == NULL)
    {
      travnode-&gt;right = node::create(elem);
      return true;
    }
    else
          travnode = travnode-&gt;right;

      }
      else 
         return false;
 } 

  /*  findKthInorder 
  @param mynode [in]     -- the root of tree whose kth largest is to be found
  @param k [in]          -- value k
  @param count [in]      -- a counter to keep track of which node we're in
  @param result [in,out] -- returns mynode-&gt;elem once we're in kth node
  */
  void findKthInorder(const node *mynode, const int k, int &amp;count,  int &amp;result) const   
  {
    if(mynode != NULL) 
    {
      findKthInorder(mynode-&gt;left,k,count,result);
      if(!--count)  
      {
        result = mynode-&gt;elem;
    return;
      } // if (!--count)

      findKthInorder(mynode-&gt;right,k,count,result);
    } // if (mynode != NULL)
  } // findKthInorder


  /* findKthInorder 
     abstracts away previous function and is exposed to outside world
  */
  int findKthInorder(const int k) const 
  {
    int count = k,result = 0;
    findKthInorder(root,k,count,result);
    return result;

   }

}; // class tree


Here's some test code that I wrote:

int main()
{
   tree T = tree(5);   
   T.insert(1); T.insert(7);   T.insert(-1);T.insert(6);

   for(int i = 1;i != 5; ++i)  
       printf("%d, " T.findKthInorder(i)); // -1, 1,5,6,7
   return 0;
}


I'll be happy to listen to any suggestions for a more  elegant findKthInorder() function.
If you add a total count field to each node, you can find the k-th element efficiently (in logarithmic time) by writing a method like this (untested):

node *kth(int k)
{
    assert(k &gt;= 0 &amp;&amp; k &lt; total);

    if (left != NULL) {
        if (k &lt; left-&gt;total)
            return left-&gt;kth(k);
        k -= left-&gt;total;
    }

    if (k == 0)
        return this;

    assert(right != NULL);
    return right-&gt;kth(k - 1);
}


Otherwise, the recursive algorithm you used for findKthInorder is the most elegant way I can think of to do this.  I would clean it up a bit, though:

static const Node *kth_(const Node *node, int &amp;k)
{
    if (node == NULL)
        return NULL;

    const Node *tmp = kth_(node-&gt;left, k);
    if (tmp != NULL)
        return tmp;

    if (k-- == 0)
        return node;

    return kth_(node-&gt;right, k);
}

int kth(int k) const
{
    assert(k &gt;= 0);

    const Node *node = kth_(this, k);
    if (node == NULL) {
        std::cerr &lt;&lt; "kth: k is too large\n";
        exit(1);
    }

    return node-&gt;elem;
}


Returning a node pointer instead of an element from the helper function has two advantages:


We can use NULL to indicate failure.
We get to drop an argument from the helper function.
In the future, it will be easier to write a function to update the kth element.


In your findKthInOrder helper function, the k argument is never actually used, and can be dropped as well.

A couple cleanups on the side:


I renamed the class node to Node to avoid having to say mynode all over the place.  I suppose this is just a matter of taste, seeing how the STL uses lowercase type names.
I switched to zero-based indexing.  Again, this is a matter of taste, but zero-based indexing is far more common in C++, and is easier to work with in many cases.