C++ program to find second largest element in binary search tree














































C++ program to find second largest element in binary search tree



/* Description
In this C++ module, we are seeing a program designed to find out the second largest element in a Binary Search Tree. For that purpose we will first create a binary search tree and then find the second largest element out of it. Since in a binary tree the element stored at right sub tree is always greater so we'll start from the right sub tree's leaf and then traverse backwardsto get the second largest element in shortest time period i.e. at second approach(c=2). This code is formatted in C++11 using stdlib functions.
*/



//PROGRAM

/* inclusion of header file*/
#include <iostream>
template<class t>

class BSTNode1{
//class to create nodes
public:
t data;
BSTNode1 *left,*right;
BSTNode1(t d)
//constructor formed
{
data=d;
left=
NULL;
right=
NULL;
}
~ BSTNode1(){}
//destructor formed
};


/*function to create binary search tree*/
template<class t>
void createBST(BSTNode1<t> *root,BSTNode1<t> *node){

t data=node->data;
if(data<root->data){
if(root->left!=NULL)
createBST(root->left,node);
else
root->left=node;
}
else{
if(root->right!=NULL)
createBST(root->right,node);
else
root->right=node;
}

}


/*function to find the second largest element out of the entire BST*/
template<class t>
void secondLargestUtil(BSTNode1<t> *root, int &c)
{

if (root == NULL || c >= 2) //condition applied to avoid recursive calls
return;
secondLargestUtil(root->right, c);
c++;
//increment count of visited nodes
if (c == 2)
{
std::cout << "2nd largest element is :" << root->data ;
return;
}
secondLargestUtil(root->left, c);
//recur for left sub-tree
}

template<class t>
void secondLargest(BSTNode1<t> *root)
{


int c = 0;
secondLargestUtil(root, c);
}

int main()
{
int option;
std::cout<<"1.char\n2.int";
std::cin>>option;

/*to switch between integer or character data type*/
if(option==2){
BSTNode1<
int> *root=NULL;
int data;
int choice=1;
while(choice==1){
std::cout<<"enter data:";
std::cin>>data;
BSTNode1<
int> *node=new BSTNode1<int>(data);
if(root==NULL){
root=node;
}
else{
createBST(root,node);
}
std::cout<<"do u want to exit,press 0....press 1 for continue";
std::cin>>choice;
}secondLargest(root);
}
else
{
BSTNode1<
char> *root1=NULL;
char data1;
int choice1=1;
while(choice1==1){
std::cout<<"enter data";
std::cin>>data1;
BSTNode1<
char> *node=new BSTNode1<char>(data1);
if(root1==NULL)
root1=node;
else
createBST(root1,node);
std::cout<<"for continue press 1";
std::cin>>choice1;
}
secondLargest(root1);
}
return 0;
}
/*
INPUT

First of all we%u2019ll switch between the integer and character type of elements. Here in this example, let us take the case of integer elements. So we enter 2.
Now, we%u2019ll enter the data.
Let it be%u2026.10
20
30
40
50

OUTPUT
2nd largest element is: 40




Now if we take an example of character elements, we%u2019ll have to enter 1.
Then, let the elements be a, s, d, f and g. then output will be.... 2nd largest element will be g


*/

More Articles of Himanshu Singh rajawat:

Name Views Likes
C++ program to find second largest element in binary search tree 168 1

Comments