Answered! Given a Binary search tree, implement a function to find the k'th largest element in the Binary search tree….

#include <iostream>
using namespace std;

struct Node {
int data;
Node *left, *right;
};

Node *newNode(int key) {
Node *node = new Node;
node->data = key;
node->left = node->right = nullptr;

return node;
}

void inorder(Node *root) {
if (root == nullptr)
return;

inorder(root->left);
cout << root->data << ” “;
inorder(root->right);
}

Node *insert(Node *root, int key) {

if (root == nullptr)
return newNode(key);

if (key < root->data)
root->left = insert(root->left, key);

else
root->right = insert(root->right, key);

return root;
}

bool search(Node *root, int key) {

while (root) {

if (key < root->data)
root = root->left;
else if (key > root->data)
root = root->right;

else
return true;
}

return false;
}

int kthLargest(Node *root, int *i, int k) {

if (root == nullptr)
return INT_MAX;

int left = kthLargest(root->right, i, k);

if (left != INT_MAX)
return left;

if (++*i == k)
return root->data;

return kthLargest(root->left, i, k);
}

int kthLargest(Node *root, int k) {

int i = 0;

return kthLargest(root, &i, k);
}

// main function
int main() {
// Test Case 1
Node *root = nullptr;
int keys[] = {15, 10, 20, 8, 12, 16, 25};

for (int key : keys)
root = insert(root, key);

int k = 2;
int res = kthLargest(root, k);

if (res != INT_MAX)
cout << res << endl;
else
cout << “Invalid Input” << endl;

// Test Case 2
root = nullptr;
int keys1[] = {2, 23, 55, 21, 313, 23, 121, 2121, 33, 1, 13, 754, 45};

for (int key : keys1)
root = insert(root, key);

k = 1;
res = kthLargest(root, k);

if (res != INT_MAX)
cout << res << endl;
else
cout << “Invalid Input” << endl;

// Test Case 3
root = nullptr;
int keys2[] = {15, 10, 20, 8, 12, 16, 25};

for (int key : keys2)
root = insert(root, key);

k = 5;
res = kthLargest(root, k);

if (res != INT_MAX)
cout << res << endl;
else
cout << “Invalid Input” << endl;
return 0;
}

Output: –

20
2121
12

——————————–
Process exited after 0.211 seconds with return value 0
Press any key to continue . . .