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.

kth maximum element in a binary search tree

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

kth maximum element

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)