Question: WAP to find Kth minimum element in a Binary Searth Tree.

Answer:

Count number of nodes in the tree if they are less then k return.
If (no_of_nodes(node->left) == k-1) return node->data
If (no_of_nodes(node->left) >= k) findkthmin(node->left,k)
else findkthmin(node->right, (k - no_of_nodes(node->left) -1))

Code:

  
#include<stdio.h>
#include<malloc.h>

struct treenode{
    int data;
    struct treenode * left;
    struct treenode * right;
};

int no_of_nodes(struct treenode * node)
{
    if(node == NULL) 
        return 0;
    else 
        return(1 + no_of_nodes(node->left) + no_of_nodes(node->right));
}

int findkthmin(struct treenode * node, int k)
{
    int no_nodes = no_of_nodes(node->left);
    if (no_nodes == k-1) 
    return node->data;
    if (no_nodes >= k) 
        return findkthmin(node->left,k);
    else 
        return findkthmin(node->right, (k - no_nodes - 1));
}

void main()
{
    struct treenode * tree;
    int k, min;
    tree = createtree(); /*create a BST*/
    scanf("%d",&k);
    if (no_of_nodes(tree) < k) 
    {
        printf("Number of nodes in tree are less than %d \n",k);
        return;
    }
    min = findkthmin(tree, k);
    printf("kth min element = %d\n",min);
}

This solution can be optimized by saving the no of nodes in each subtree while calling no_of_nodes(tree) for root.

For finding kth maximum element, similar logic can be used.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.