### C++ program to find K th largest element in binary search tree when tree modification is not allowed

TOPIC: C++ program to find K'th largest element in a binary search tree when tree modification is not allowed.

DESCRIPTION:

As we all know that in a BST the INORDER gives ASCENDING ORDER of all the nodes in the tree and in INORDER we traverse left subtree first then the root and then finally the right subtree.

So we can easily find the k'th largest element from this by knowing the size of the tree beforehand BUT let's make the calculations more easy and understandable.

If we modify this INORDER where instead of traversing the left subtree first we are traversing the right subtree first the result will be interesting, which is actually DECREASING ORDER of all the nodes available in the BST.

Let's name this type of INORDER approach as REVERSE INORDER.

Therefore, here we will proceed following.

REVERSE INORDER - Right Subtree , root, Left Subtree

And at each recursive approach, the basis or the terminating or the base case will be when the root visited becomes NULL.

PROCEDURE REVERSE_INORDER

One static variable let's say 'i' which will increase each time we visit a node if the value 'i' is equal to Kth value then we will print that node value and we will keep increase 'i'

Static int i = 1

Static bool found =false

Case 1. If the root is NULL that is there is no node to delete.

Return found

Case 2. Call this procedure to the right subtree of the root.

Call this procedure to the left subtree of the root.

If i is equal to k then print roots value and found = true

i++

Lets take an example to clarify, consider this tree: -

Its normal inorder would be 1,2,4,5,7,8,10

Here the 3rd largest node will be (size-3rd) +1 element, see here we have to find the size also.

And its reverse inorder would be 10,8,7,5,4,2,1

Here the 3rd largest node will be the 3rd element itself.

------------------------------------------------------------------------------------------------------------------------------------------------------------

Complexity

Worst case O(n) k value is bigger than the size of the tree.

We can definitely decrease the complexity by switching the control to the main as soon as we find the desired node, in that case, the best case would be O(1) i.e. when the k has the value equal to the size of the tree. I have also included the less complex code in my git repository, check it out at

https://github.com/pyskmr/D4datastructures/blob/master/binary%20search%20tree/kthlargest_optimised.cpp

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I always put an emphasis on coding on your own but I'm still providing you the code just in case you need some help.

CODE:-

 ` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169` `#include/*C++ program to find K'th largest element in binary search tree when tree modification is not allowed*/using namespace std;/*a base class is created which contain the data of every node in the tree*/templateclass node { public: T data; node *left; node *right; node();};/*construtcor of the base class*/templatenode::node(){ data=0; left=right=NULL;}/*class tree inheriting node class and having a root object of the node as its class member */templateclass tree: public node { private: node *root; public: tree(); node* getroot(); void insert(S); bool reverse_Inorder(node *,const int&);};/*tree class default constructor.As soon as the object will be made its root will be pointed to NULL*/templatetree::tree() { root=NULL;}/*tree class parameterized constructor ,just in case if we know the value of the node at its declaration*/templatenode* tree::getroot() { return root;}/*Insertion member function*/templatevoid tree :: insert(S value) { node *temp = new node; temp->data = value; /*if root is not pointing to anything ,that is tree is not existing*/ if(root == NULL) { root=temp; } else { node *current=root; node *prev = NULL; while(current) { /*storing the last node visited because at the end the pointer will point to the null*/ prev=current; /* If item is greater than current node go to right sub tree */ if(temp->data > current->data) { current=current->right; } /* If item is samller than current node go to left sub tree */ else { current=current->left; } } /*last node in comparison*/ /*if the data is more make the new node as right child*/ if (temp->data > prev->data) { prev->right = temp; } /*if new node data is less make it left child*/ else { prev->left = temp; } }} /*tree traversing using reverse_Inorder approach i.e. we will traverse right subtree and then left subtree of the current */templatebool tree::reverse_Inorder(node* p,const int &count) { /* this will be incremented and compared to count and when they are equal we will how that our kth largest node is found */ static int i=1; /* this is a flag whih will tell if the value exist or not */ static bool found_status= false; if(p==NULL || count <1) { return found_status ; } reverse_Inorder(p->right,count); if(i==count) { cout<<"node value is "<data<left,count);}/*main function*/int main(int argc, char const *argv[]){ /* tree object */ tree obj; /* some initialisation.You can also insert by asking to the user but i did so to make the things more clear */ obj.insert(5); obj.insert(2); obj.insert(8); obj.insert(4); obj.insert(1); obj.insert(7); obj.insert(10); /* value of K is taken */ int K; cout<<"Enter value of K "; cin>>K; /* procedure called, if it wont find the node it will return false */ if(!obj.reverse_Inorder(obj.getroot(),K)) { cout<<"Element not found\n"<

`OUTPUT :-`

 `KEEP UP THE GOOD WORK AND KEEP CODING. (:`