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:

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;