Find kth smallest element in a Binary Search tree in C++

In this tutorial, we are going to find the kth smallest value in a Binary Search tree in C++. We assume that we are given the root node of the tree and the value of k. We can approach this problem with various methods. For instance, the Inorder Tree Traversal traverses the nodes in ascending order. So the idea is to traverse the tree by Inorder traversal.

We can use an array to store each traversed element. Now print out the element at index (k-1) to get the desired answer but this is not an efficient approach since for any value of k we have to traverse the entire tree. Instead, we can keep track of the inorderly traversed nodes and stop when we get the desired answer

Approach:

  • We traverse the tree by Inorder traversal. Since it visits the nodes in ascending order of their values, we visit the smallest element of the entire bst first.
  • As we visit the nodes in ascending order, we decrement the value of k after visiting each node.
  • We pass the value of k by reference, to remember the value of k in each step as the recursion unfolds.
  • After decrementing the value of k, we check whether it is Zero. If it is Zero we print the node value. Suppose we need to visit the 2nd smallest node i.e k=2. We visit the smallest node and decrement the value of k, now k=1, then we visit the 2nd smallest node and decrement the value of k, now k=0. We print the node value.
  • When k=0, we return the function, to avoid unnecessary further traversal of the tree.

 

Example:

Suppose we are given the following binary search tree and the value of k is 3.

binary search tree

We pass on k=3 and the address of the root node to our function.

  1. The first node to be visited will be the node with value 1. The value of k is decremented by 1, therefore k=2.
  2. The second node to be visited will be the node with value 4. The value of k is decremented by 1, therefore k=1.
  3. The third node that we will visit will be the node with value 6. The value of k is decremented by 1, therefore k=0.
  4. Since the value of k=0, we print the node value i.e 6.
  5. We return the function to avoid further tree traversal.

 

C++ implementation to find the kth smallest element in a bst:

#include<iostream>
using namespace std;

//structure to build node of a binary search tree
struct node
{
    int info;
    struct node *llink;
    struct node *rlink;

};

//Recursive function to build a bst.
struct node* createbst(struct node* root,int data)    
{
  if(root==NULL)
  {
     root=(struct node*)malloc(sizeof(struct node*));
     root->info=data;
     root->llink=root->rlink=NULL;
     return root;
  }
  else{
   if(root->info<data)
    root->rlink=createbst(root->rlink,data);
    else if(root->info>data)
    root->llink=createbst(root->llink,data);
    else
    cout<<"duplicate element"<<endl;
    return root;
  }
}

//function to find out kth smallest element.
// k is passed by reference to remember it's value over recursion.
void findkelement(struct node* t,int &k)     
{                                           
    if(t==NULL||k<0)
        return;
    findkelement(t->llink,k);
    --k;
    if(k==0){
        cout<<t->info;
        return;
    }
    findkelement(t->rlink,k);
}
int main()
{
 int data,n;
 //Initially setting root value to NULL for an empty tree
 struct node *root=NULL;
 cout<<"enter no. of nodes"<<endl;
 cin>>n;
 cout<<"enter the node values"<<endl;
 for(int i=0;i<n;i++)
 {
  cin>>data;
//fuction call to createbst function to build a binary search tree   root=createbst(root,data);
 }
 cout<<"enter value of k"<<endl;
 int k;
 cin>>k;
 cout<<"the kth smallest element is : ";  
//function call to the function to find kth smallest element.                                       
 findkelement(root,k);

}

 

Output :

enter no. of nodes
5
enter the node values
8
3
10
1
6
enter value of k
3
the kth smallest element is : 6

Time complexity: The time complexity will be O(n) if the given bst is a skewed tree then to find out the kth smallest element we need to traverse the entire binary search tree.

 

 

Leave a Reply