Find k-th smallest element in Binary Search Tree

Given root of the tree and k as input, output K th smallest element. for example in below given tree, for k=3 we will get 5.

The idea simple do inorder traversal store it an array and as we know by the property of the binary search tree inorder traversal gives element of a binary search tree in sorted form.

We will explore two approaches:

  • Using inorder traversal (O(N))
  • Efficient approach (O(log N))

Algorithm 1: Using inorder traversal O(N)

  1. Do the Inorder traversal of the Binary search tree and store the elements in an vector as come in sequence.
  2. Then from sorted vector made from above process return the k-th element and it is the output we need.

Below is the Implementation of the above algorithm.

#include <bits/stdc++.h>
using namespace std;
struct node 
{ 
    int key; 
    struct node *left, *right; 
}; 
  
// A utility function to create a new BST node 
struct node *newNode(int item) 
{ 
    struct node *temp =  (struct node *)malloc(sizeof(struct node)); 
    temp->key = item; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key) 
{ 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left  = insert(node->left, key); 
    else if (key > node->key) 
        node->right = insert(node->right, key);    
  
    /* return the (unchanged) node pointer */
    return node; 
} 
/* This function traverse the skewed binary tree and 
   stores its nodes pointers in vector nodes[] */
void storeBSTNodes(struct node* root, vector<struct node*> &nodes) 
{ 
    // Base case 
    if (root==NULL) 
        return; 
  
    // Store nodes in Inorder (which is sorted 
    // order for BST) 
    storeBSTNodes(root->left, nodes); 
    nodes.push_back(root); 
    storeBSTNodes(root->right, nodes); 
} 
  
/* Recursive function to construct binary tree */
  
// This functions find Kth Minimum Element in BST
int findKthMinimumElement(struct node* root,int k) 
{ 
    // Store nodes of given BST in sorted order 
    vector<struct node*> nodes; 
    storeBSTNodes(root, nodes); 
 
    return nodes[k-1]->key;
} 
// Driver Program to test above functions 
int main() 
{ 
    int k =3;
    struct node *root = NULL; 
    root = insert(root, 6); 
    insert(root, 4); 
    insert(root, 5); 
    insert(root, 3); 
    insert(root, 8); 
    insert(root, 9); 
    cout<<"The "<<k<<" th smallest element in Binary search tree is "<<findKthMinimumElement(root,k);
} 

Output:

The 3 th smallest element in Binary search tree is 5

Explanation:

Time Complexity:

Inorder Traversal of Binary search Tree takes O(n) time and fetching the K th element from vector requires O(1) time. Therefore, all over time complexity of this algorithm is O(n).

Efficient Approach O(log N)

The idea to maintain the the rank of each node. we will count the number of nodes in the left subtree of each node so this will give the rank of the node. It will help us to find the element in o(h) time. see below algorithm for more understanding. Algorithm:

start:
if K = root.leftElement + 1
   root node is the K th node.
   goto stop
else if K > root.leftElements
   K = K - (root.leftElements + 1)
   root = root.right
   goto start
else
   root = root.left
   goto start
stop:

Implementation of above algorithm in c++

#include <bits/stdc++.h>
using namespace std;
  
typedef struct node node; 
  
/* Binary tree node */
struct node 
{ 
    int data; 
    int lCount; 
  
    node* left; 
    node* right; 
}; 
 
 node *newNode(int item) 
{ 
    
         node *new_node = (node *)malloc( sizeof(node) ); 
  
        /* initialize */
        new_node->data   = item; 
        new_node->lCount = 0; 
        new_node->left   = NULL; 
        new_node->right  = NULL; 
        
        return new_node;
} 
/* Iterative insertion 
   Recursion is least preferred unless we gain something 
*/
node *insert(node *root, int data)
{ 
    node *node_t = newNode(data);
    /* A crawling pointer */
    node *pTraverse = root; 
    node *currentParent = root; 
  
    // Traverse till appropriate node 
    while(pTraverse) 
    { 
        currentParent = pTraverse; 
  
        if( node_t->data < pTraverse->data ) 
        { 
            /* We are branching to left subtree 
               increment node count */
            pTraverse->lCount++; 
            /* left subtree */
            pTraverse = pTraverse->left; 
        } 
        else
        { 
            /* right subtree */
            pTraverse = pTraverse->right; 
        } 
    } 
  
    /* If the tree is empty, make it as root node */
    if( !root ) 
    { 
        root = node_t; 
    } 
    else if( node_t->data < currentParent->data ) 
    { 
        /* Insert on left side */
        currentParent->left = node_t; 
    } 
    else
    { 
        /* Insert on right side */
        currentParent->right = node_t; 
    } 
  
    return root; 
} 
  
int findKthMinimumElement(node *root, int k) 
{ 
    int ret = -1; 
  
    if( root ) 
    { 
        /* A crawling pointer */
        node *pTraverse = root; 
  
        /* Go to k-th smallest */
        while(pTraverse) 
        { 
            if( (pTraverse->lCount + 1) == k ) 
            { 
                ret = pTraverse->data; 
                break; 
            } 
            else if( k > pTraverse->lCount ) 
            { 
                /*  There are less nodes on left subtree 
                    Go to right subtree */
                k = k - (pTraverse->lCount + 1); 
                pTraverse = pTraverse->right; 
            } 
            else
            { 
                /* The node is on left subtree */
                pTraverse = pTraverse->left; 
            } 
        } 
    } 
  
    return ret; 
} 
  
/* Driver program to test above functions */
int main(void) 
{ 
   int k =3;
    node *root = NULL; 
    root = insert(root, 6); 
    root=insert(root, 4); 
    root=insert(root, 5); 
    root=insert(root, 3); 
    root=insert(root, 8); 
    root=insert(root, 9); 
    cout<<"The "<<k<<" th smallest element in Binary search tree is "<<findKthMinimumElement(root,k);
    return 0; 
} 

Explanation:


This is a companion discussion topic for the original entry at http://iq.opengenus.org/find-k-th-smallest-element-in-binary-search-tree/