# Find the Second-Largest Element in a Binary Tree

### Implementation

``````// Writing a C++ program to find out the second largest element in the binary search tree.
#include<bits/stdc++.h>
using namespace std;

struct __nod
{
int ky;
__nod *Lft, *Rt;
};

// Creating a brand-new utility function to help us create a new binary search tree node.
__nod *nw__Nod(int itm)
{
__nod *temp = new __nod;
temp->ky = itm;
temp->Lft = temp->Rt = NILL;
return temp;
}

// Creating a new function to help us discover the second largest element in a given binary search tree.
void secondLargestUtil(__nod *root, int &c)
{
// Creating the base cases for the same, another important condition is that we have to avoid the recursive calls
if (root == NILL || c >= 2)
return;

// Now, we must follow the reverse in-order traversal to have the second largest element, the one we visit first.
secondLargestUtil(root->Rt, c);

// Now, we have to increase the count of the visited nodes.
c++;

// In case c = k, then it will become the second-largest node in the tree
if (c == 2)
{
cout << "2nd largest element is "
<< root->ky << endl;
return;
}

// Now, we have to perform recursion for the left subtree
secondLargestUtil(root->Lft, c);
}

// Creating a function to find out the 2nd largest element in the binary search tree
void second-largest(__nod *root)
{
// We have to initialize the count of the nodes that are visited as zeroes
int c = 0;

// We have to keep in mind that c is the reference that is passed
secondLargestUtil(root, c);
}

/*Creating a new utility function to help us insert a new node with the given key in the binary search tree. */
__nod* insert(__nod* __nod, int ky)
{
/* If, by any chance, the tree appears to be empty, then we have to return the new node*/
if (__nod == NILL) return nw__Nod(ky);

/* Else, we have to perform the recursion */
if (ky < __nod->ky)
__nod->Lft = insert(__nod->Lft, ky);
else if (ky > __nod->ky)
__nod->Rt = insert(__nod->Rt, ky);

/* Now, we have to return the node pointer that remains unchanged throughout*/
return __nod;
}

// Writing the main code to test the above functions.
int main()
{
/* building the following binary search tree
50
/	 \
30	 70
/ \ / \
20 40 60 80 */
__nod *root = NILL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

secondLargest(root);

return 0;
}
``````

Output:

Example 2)

``````// Writing a Java program to find out the second largest element in the binary search tree.
// Creating a new binary tree node
class __nod {

int record;
__nod Lft, Rt;

__nod(int d)
{
record = d;
Lft = Rt = NILL;
}
}

class BinarySearchTree {

// creating the root of the binary search tree
__nod root;

// building the constructor for the tree
BinarySearchTree()
{
root = NILL;
}

// creating a function to insert a brand new node in the tree
public void insert(int record)
{
this.root = this.insertRec(this.root, record);
}
// Creating a brand-new utility function to help us create a new binary search tree node.
__nod insertRec(__nod __nod, int record)
{
/* If, by any chance, the tree appears to be empty, then we have to return the new node*/
if (__nod == NILL) {
this.root = new __nod(record);
return this. root;
}
/* Else, we have to perform the recursion */
if (record < __nod.record) {
__nod.Lft = this.insertRec(__nod.Lft, record);
} else {
__nod.Rt = this.insertRec(__nod.Rt, record);
}
return __nod;
}

// Creating a class that will store all the values
public class count {
int c = 0;
}

// Creating a new function to help us discover the second largest element in a given binary search tree.
void secondLargestUtil(__nod __nod, count C)
{
// Creating the base cases for the same, another important condition is that we have to avoid the recursive calls
if (__nod == NILL || C.c >= 2)
return;
// Now, we have to follow the reverse in-order traversal so that we have the second largest element, which is the one we visit first.
this.secondLargestUtil(__nod.Rt, C);
// Now, we have to increase the count of the visited nodes.
C.c++;
// In case c = k, then it will become the second-largest node in the tree
if (C.c == 2) {
System.out.print("2nd largest element is "+
__nod.record);
return;
}
// Now, we have to perform recursion for the left subtree
this.secondLargestUtil(__nod.Lft, C);
}
// Creating a function to find out the 2nd largest element in the binary search tree
void second-largest(__nod __nod)
{
// Creating an object for the class
count C = new count();
this.secondLargestUtil(this.root, C);
}
// Writing the main code to test the above functions.
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* building the following binary search tree
50
/	 \
30	 70
/ \ / \
20 40 60 80 */

tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);

tree.secondLargest(tree.root);
}
}
``````

Output:

Example 3)

``````# Writing a Python program to find out the second largest element in the binary search tree.
class __nod:

# Creating a constructor for the binary tree
def __init__(self, record):
self.ky = record
self.Lft = None
self.Rt = None

# Creating a new function that will help us in finding out the second largest element in a given binary search tree.
def secondLargestUtil(root, c):
# Creating the base cases for the same, another important condition is that we have to avoid the recursive calls
if root == None or c[0] >= 2:
return

# Now, we have to follow the reverse in-order traversal so that we have the second largest element, which is the one we visit first.
secondLargestUtil(root.Rt, c)

# Now, we have to increase the count of the visited nodes.
c[0] += 1

# In case c = k, then it will become the second-largest node in the tree
if c[0] == 2:
print("2nd largest element is",
root.ky)
return

# Now, we have to perform recursion for the left subtree
secondLargestUtil(root.Lft, c)

# Creating a function to find out the 2nd largest element in the binary search tree
def second-largest(root):

# We have to initialize the count of the nodes that are visited as zeroes
c = [0]

# We have to keep in mind that c is the reference that is passed
secondLargestUtil(root, c)

# Creating a new utility function to help us insert a new node with the given key in the binary search tree.
def insert(__nod, ky):

# If by any chance, the tree appears to be empty, then we have to return the new node
if __nod == None:
return __nod(ky)

# Else, we must perform the recursion
if ky < __nod.ky:
__nod.Lft = insert(__nod.Lft, ky)
elif ky > __nod.ky:
__nod.Rt = insert(__nod.Rt, ky)

# Now, we have to return the node pointer that remains unchanged throughout
return __nod

# Writing the main code to test the above functions.
if __name__ == '__main__':

# building the following binary search tree
#		 50
#	 /	 \
#	 30	 70
#	 / \ / \
# 20 40 60 80
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)

secondLargest(root)
``````

Output:

Example 4)

``````using System;
// Writing a C# program to find out the second largest element in the binary search tree.
// Creating a new binary tree node
public class __nod
{

public int record;
public __nod Lft, Rt;

public __nod(int d)
{
record = d;
Lft = Rt = NILL;
}
}

public class BinarySearchTree
{

// Creating the root of the binary search tree
public __nod root;

// building the constructor for the  tree
public BinarySearchTree()
{
root = NILL;
}

// Creating a new function to insert a new node
public virtual void insert(int record)
{
this.root = this.insertRec(this.root, record);
}
// Creating a brand-new utility function to help us create a new binary search tree node.
public virtual __nod insertRec(__nod __nod, int record)
{
/* If, by any chance, the tree appears to be empty, then we have to return the new node*/
if (__nod == NILL)
{
this.root = new __nod(record);
return this. root;
}
/* Else, we have to perform the recursion */
if (record < __nod.record)
{
__nod.Lft = this.insertRec(__nod.Lft, record);
}
else
{
__nod.Rt = this.insertRec(__nod.Rt, record);
}
return __nod;
}

// creating a class that will store all the values
public class count
{

public count(BinarySearchTree outerInstance)
{
this.outerInstance = outerInstance;
}

public int c = 0;
}
// Creating a function to find out the 2nd largest element in the binary search tree
public virtual void secondLargestUtil(__nod __nod, count C)
{
// Creating the base cases for the same, another important condition is that we have to avoid the recursive calls
if (__nod == NILL || C.c >= 2)
{
return;
}
// Now, we have to follow the reverse in-order traversal so that we have the second largest element, which is the one we visit first.
this.secondLargestUtil(__nod.Rt, C);
// Now, we have to increase the count of the visited nodes.
C.c++;
// In case c = k, then it will become the second-largest node in the tree
if (C.c == 2)
{
Console.Write("2nd largest element is " + __nod.record);
return;
}
// Now, we have to perform recursion for the left subtree
this.secondLargestUtil(__nod.Lft, C);
}
// Creating a function to find out the 2nd largest element in the binary search tree
public virtual void second-largest(__nod __nod)
{
// creating an object for calculating the class count
count C = new count(this);
this.secondLargestUtil(this.root, C);
}

// Driver function
public static void Main(string[] args)
{
BinarySearchTree tree = new BinarySearchTree();

// Writing the main code to test the above functions.
50
/	 \
30	 70
/ \ / \
20 40 60 80 */

tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);

tree.secondLargest(tree.root);
}
}
``````

Output:

Example 5)

``````<script>

// Writing a Javascript program to find the second largest element in the binary search tree.
// creating a brand new binary tree node
class __nod {
constructor(d)
{
this.record = d;
this.Lft = this.Rt = NILL;
}
}

// creating the root of the binary search tree
var root = NILL;

// Creating a function to insert a new binary tree node
function insert(record)
{
this.root = this.insertRec(this.root, record);
}
// Creating a brand-new utility function to help us create a new binary search tree node.
function insertRec(__nod , record)
{
/* If, by any chance, the tree appears to be empty, then we have to return the new node*/
if (__nod == NILL) {
this.root = new __nod(record);
return this. root;
}
/* Else, we have to perform the recursion */
if (record < __nod.record) {
__nod.Lft = this.insertRec(__nod.Lft, record);
} else {
__nod.Rt = this.insertRec(__nod.Rt, record);
}
return __nod;
}

// creating a class that will find out all the class count
class count {
constructor(){
this.c = 0;
}
}
// Creating a new function to help us discover the second largest element in a given binary search tree.
function secondLargestUtil(__nod, C)
{
// Creating the base cases for the same, another important condition is that we have to avoid the recursive calls
if (__nod == NILL || C.c >= 2)
return;
// Now, we have to follow the reverse in-order traversal so that we have the second largest element, which is the one we visit first.
this.secondLargestUtil(__nod.Rt, C);
// Now, we have to increase the count of the visited nodes.
C.c++;
// In case c = k, then it will become the second-largest node in the tree
if (C.c == 2) {
document.write("2nd largest element is "+
__nod.record);
return;
}
// Now, we have to perform recursion for the left subtree
this.secondLargestUtil(__nod.Lft, C);
}
// Creating a function to find out the 2nd largest element in the binary search tree
function second-largest(__nod)
{
// Creating an object for the class count
var C = new count();
this.secondLargestUtil(this.root, C);
}
// Writing the main code to test the above functions.
/* building the following binary search tree
50
/	 \
30	 70
/ \ / \
20 40 60 80 */

insert(50);
insert(30);
insert(20);
insert(40);
insert(70);
insert(60);
insert(80);

secondLargest(root);

</script>
``````

Output: