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