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














































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.


Link to source code:  https://github.com/pyskmr/D4datastructures/blob/master/binary%20search%20tree/kthlargest.cpp



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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<iostream>

/*

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*/
template<class T>
class node
{
public:

T data;
node *left;
node *right;


node();
};

/*construtcor of the base class*/
template<class T>
node<T>::node()
{
data=0;
left=right=NULL;
}

/*class tree inheriting node class and having a root object of the node as its class member */
template<class S>
class tree: public node<S>
{
private:

node<S> *root;

public:
tree();
node<S>* getroot();
void insert(S);
bool reverse_Inorder(node<S> *,const int&);
};


/*tree class default constructor.As soon as the object will be made its root will be pointed to NULL*/
template<class S>
tree<S>::tree()
{
root=NULL;
}

/*tree class parameterized constructor ,just in case if we know the value of the node at its declaration*/
template<class S>
node<S>* tree<S>::getroot()
{
return root;
}

/*Insertion member function*/
template<class S>
void tree <S>:: insert(S value)
{
node<S> *temp = new node<S>;
temp->data = value;

/*if root is not pointing to anything ,that is tree is not existing*/
if(root == NULL)
{
root=temp;
}

else
{
node<S> *current=root;
node<S> *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 */
template<class S>
bool tree<S>::reverse_Inorder(node<S>* 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 "<<p->data<<endl;
found_status=true;
}
i++;

reverse_Inorder(p->left,count);
}

/*main function*/
int main(int argc, char const *argv[])
{
/* tree object */
tree<int> 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"<<endl;
}

return 0;
}


OUTPUT :-




KEEP UP THE GOOD WORK AND KEEP CODING. (:

Comments