Kth Largest and Smallest in Binary Search Tree | Part2

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 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

 

Sree Hari Sanjeev

The founder and CEO of Wisdom Overflow. His enthusiasm and effort has taken the blog to next level. You will be motivated just by taking a look at his daily schedule.

Leave a Reply

Your email address will not be published.

four + 2 =