Given a Binary search tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.

Example 1:

```Input:
4
/   \
2     9
k = 2
Output: 4
```

Example 2:

```Input:
9
\
10
K = 1
Output: 10
```

method:

1. The idea is to do reverse inorder traversal of BST and save all the nodes data in a vector
2. the inorder traversal will save the tree nodes in increasing order in vector
3. now traverse from backside through vector and and output the kth element from back

c++ implementation:

```vector<int>v;
void printInorder(struct Node* node)
{
if (node == NULL)
return;

printInorder(node->left);

v.push_back(node->data);

printInorder(node->right);
}

int kthLargest(Node *root, int k)
{

vector<int>::iterator i;
printInorder(root);

while(k!=1)
{
v.pop_back();
k--;
}
int c=v.back();
return c;
}
};```

1. Time Complexity: O(h + k).
The code first traverses down to the rightmost node which takes O(h) time, then traverses k elements in O(k) time. Therefore overall time complexity is O(h + k).
2. Auxiliary Space: O(h)
where h is the height of the tree.

fghjkl;
darkmode