Finding the kth smallest value in a BST

Question

Here is what I have to find the kth smallest value in a binary search tree:

struct treeNode 
{
   int data;
   struct treeNode *left, *right:
};

int rank(stuct treeNode* ptr, int k)
{
   if(node == NULL)
    return root; 

   while(ptr->left != NULL) {
     ptr = ptr->left;
     return rank(ptr->left)
   }
}

This is obviously not correct. Without providing the solution, could someone guide me in the right direction as to how I could solve this? I am having trouble figuring out how I could find the kth smallest element in a BST.

Answer 1

A BST is a sorted binary tree, an in-order traversal (left subtree, current node, right subtree) will give sorted node values. To find the kth smallest node, just do an in-order traversal with a counter. The counter starts from 0, whenever a node is traversed, increase it by one, when it reaches k, the node is the kth smallest one.

Answer 2

If you have the sizes of each of the subtrees, this can be doable without having to read the data into an array (or otherwise traversing the tree) and counting up. If you don't keep the size information handy, you'll need a helper function to calculate the size.

The basic idea, figure out what is the index of the current node. If it is less than k, you need to search the left subtree. If it is greater than k, search the right offsetting the nodes counted from the left and current. Note that this is essentially the same as searching through a regular BST, except this time we are searching by index, not data. Some pseudocode:

if size of left subtree is equal to k:
    // the current node is kth
    return data of current node
else if size of left subtree is greater than k:
    // the kth node is on the left
    repeat on the left subtree
else if size of left subtree is less than k:
    // the kth node is on the right
    reduce k by the size of the left subtree + 1 // need to find the (k')th node on the right subtree
    repeat on the right subtree

To illustrate, consider this tree with the marked indices (don't even worry about the data as it's not important in the search):

        3
      /   \
     2     6
    /     / \
   0     4   7
    \     \
     1     5

Suppose we want to find the 2nd (k = 2).
Starting at 3, the size of the left subtree is 3.
It is greater than k so move to the left subtree.
The size of the left subtree is 2.
k is also 2 so the current node must be the 2nd.

Suppose we want to find the 4th (k = 4).
Starting at 3, the size of the left subtree is 3.
It is less than l so adjust the new k to be 0 (k' = 4 - (3 + 1)) and move to the right subtree.
Starting at 6, the size of the left subtree is 2.
It is greater than k' (0) so move to the left subtree.
The size of the left subtree is 0.
k' is also 0 so the current node must be the 4th.

You get the idea.

Answer 3

This should work:

int rank(struct treeNode* n,int k,int* chk)
    {
    if(!n) return -1;
    int _chk = 0;
    if(!chk) chk = &_chk;

    int t = rank(n->left,k,chk);
    if(t>=0) return t;

    if(++*chk > k) return n->data;

    int t = rank(n->right,k,chk);
    if(t>=0) return t;
    return -1;
    }

call as rank(root,k,0)