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
	{
		private readonly BinarySearchTree outerInstance;


		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: