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)