Program to find the kth maximum element in a binary search tree
Select Articles
Program to find the kth maximum element in a binary search tree
Program to find the kth maximum element in a binary search tree is discussed here. The binary search tree and a positive integer 'k' is given as input and the kth maximum element is produced as output.
Algorithm to find the Kth maximum element in a BST
Input the binary search tree and the K value from the user.
Find the reverse of inorder traversal of the binary search tree.
Reverse inorder traversal is done because the traversal all nodes takes place in decreasing order.
Keep track of the count of nodes visited while traversing.
When the count of the nodes becomes equal to K value, return the node.
Program to find the Kth largest element in a binary search tree is given below.
C
// C program to find the Kth maximum element in a binary search tree
#include
#include
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};
// Function to find k’th maximum element
void kth_largest(node *root, int k, int &c)
{
// Base cases
if (root == NULL || c >= k)
return;
// largest element is visited first
kth_largest(root->right, k, c);
c++; // Increment count of visited nodes
// If c == k, then this is the k’th largest
if (c == k)
{
printf(“\nK’th largest element is %d\n”,root->data);
return;
}
// Recursion for left subtree
kth_largest(root->left, k, c);
}
// Function to find k’th maximum element
void kth_largest_element(node *root, int k)
{
int c = 0;
// c is passed by reference
kth_largest(root, k, c);
}
void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
printf(“%d “, root -> data);
inorder(root -> right);
}
int main()
{
struct node *root = NULL;
int n;
printf(“\nEnter the number of edges : “);
scanf(“%d”,&n);
printf(“\nInput the tree : \n”);
while(n–)
{
char lr;
int n1,n2;
scanf(“%d”,&n1);
scanf(“%d”,&n2);
scanf(” %c”,&lr);
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
printf(“Inorder Tree Traversal : “);
inorder(root);
printf(“\n”);
int c = 0;
int k;
printf(“\nEnter the value of k : “);
scanf(“%d”,&k);
kth_largest_element(root, k);
return 0;
}
C++
// C++ program to find the Kth maximum element in a binary search tree
# include
# include
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};
// Function to find k’th maximum element
void kth_largest(node *root, int k, int &c)
{
// Base cases
if (root == NULL || c >= k)
return;
// largest element is visited first
kth_largest(root->right, k, c);
c++; // Increment count of visited nodes
// If c == k, then this is the k’th maximum element
if (c == k)
{
cout << “\nK’th largest element is ” << root>data;
return;
}
// Recursion for left subtree
kth_largest(root->left, k, c);
}
// Function to find k’th maximum element
void kth_largest_element(node *root, int k)
{
int c = 0;
// c is passed by reference
kth_largest(root, k, c);
}
void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root> data << ” “;
inorder(root -> right);
}
int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
cout << “\nInput the tree : \n”;
while(n–)
{
char lr;
int n1,n2;
cin >> n1;
cin >> n2;
cin >> lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout << “Inorder Tree Traversal : “;
inorder(root);
cout << endl>
int c = 0;
int k;
cout << “\nEnter the value of k : “;
cin >> k;
kth_largest_element(root, k);
return 0;
}
OUTPUT
Input -
Enter the number of edges : 7
Input the tree :
15 12 l
12 8 l
12 13 r
15 18 r
18 24 r
24 22 l
24 27 r
Inorder Tree Traversal : 8 12 13 15 18 22 24 27
Output -
K'th largest element is 27
K'th largest element is 24
K'th largest element is 22
K'th largest element is 18
K'th largest element is 15
K'th largest element is 13
K'th largest element is 12
Time complexity: O(n + k)
For traversing n nodes: O(n)
For traversing down to rightmost nodes: O(k)
Overall time complexity: O(n + k)
Write a public review