Kth Largest and Smallest in Binary Search Tree | Part2

Question

Write a C program to find kth largest and smallest in BST (Binary Search Tree). Create a BST and get the K from the user.

Prerequisite

We have already covered how to create a Binary search tree from the user input in Part 1: C program to create a Binary Search Tree . I recommend you to read Part1 before Part2 for better understanding.

Logic for Kth Largest

• To count the nodes we use Lcount with initial value 0.
• If we have one root node with two child, then the order of size: right child> root> left child
• Generally, the right side nodes are larger than root. So we traverse to right most child to get the largest node.
• Increment the count and check whether the count is equal to k. If equal print root->data.
• Else traverse in this order recursively : right->root->left.
• For Kth Smallest we traverse in this order: left->root->right.
• Recommended: Draw BST for the Sample inputs to understand the flow of control.

Program

[code lang=”c”]
#include<stdio.h>
/*keeping count as global to reflect changes in each function call*/
int Lcount=0; //to find kth Largest
int Scount=0; //to find kth Smallest
/*Node in tree structure*/
struct bst
{
struct bst* left; //pointer to left node
struct bst* right; //pointer to right node
int data;
};
void createBST(struct bst** root,int data)
{ /*See Part1 for complete code*/
}
void kthLargest(struct bst* root,int k)
{

if(root!=NULL)
{
kthLargest(root->right,k);
Lcount++;
if(k==Lcount)
{
printf("%d %d\n",root->data,Lcount);
return;
}
kthLargest(root->left,k);
}
}
void kthSmallest(struct bst* root,int k)
{
if(root!=NULL)
{
kthSmallest(root->left,k);
Scount++;
if(k==Scount)
{
printf("%d %d\n",root->data,Scount);
return;
}
kthSmallest(root->right,k);
}
}
int main()
{
struct bst* root =NULL;
int i,n,data;
printf("enter no. of elements");
scanf("%d",&n);
/*get n elements from user and create Binary Search Tree*/
for(i=0;i<n;i++)
{
scanf("%d",&data);
createBST(&root,data);
}
//Passing root poiner and kvalue(=3)
kthLargest(root,3);
kthSmallest(root,3);
}
[/code]

You might also like…

Print sequence of numbers without using loop