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

#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);
}

You might also like…

Print sequence of numbers without using loop