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)

- If root=null or c>= k

return. - KthLargest ( root->right , k, c)
- c++
- if ( c == k) cout << root -> n;
- KthLargest ( root->left , k, c)

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