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;
darkmode