K’th Largest Element in BST when modification to BST is not allowed

Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

      [20]
      /  \     
    [8]  [22] 
    /  \
  [5]  [10]
       /  \
     [9]  [12]

For example, in the following BST, if
if k = 3, then output should be 12
if k = 5, then output should be 9.

Method 1)  Brute Force in O(n)

In order of BST gives 5,8,9,10,12,20,22
and print member A[n-k+1] will be out put.

Now Lets discuss tricky way :

As we know that larger elements are in Right Side of a node and smaller in left side for BST.
Can we use this trick ???

Think for above example , R=no if Recursion,
r = 1 we traverse 22 and found that its largest
r = 2 we traverse 20, which is second largest.
r=3 and we went to 12 via 8-10-12 ( first traverse right path always)
     so 3rd largest is 12.

So with Post Order Traversal We can find Kth largest in O(k + h) time

So Method 2 ) Post Order Traversal 

Algo . C=Count of node visited, K= Kth number

Function KthLargest(Node *root, int k, int &c)

1. If root=null or c>= k
         return.
2. KthLargest ( root->right ,  k, c)
3. c++
4. if ( c == k) cout << root -> n;
5. KthLargest ( root->left ,  k, c)

For queries, suggestion and more questions / solutions please write us at admin@gohired.in