# Kth largest element in BST

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:

- The idea is to do reverse inorder traversal of BST and save all the nodes data in a vector
- the inorder traversal will save the tree nodes in increasing order in vector
- 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; } };

**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).**Auxiliary Space:**O(h)

where h is the height of the tree.

fghjkl;