1.
Introduction
2.
Finding the second largest element in BST
3.
Algorithm
4.
Implementation
4.1.
C++
4.2.
PYTHON
4.3.
JAVA
5.
5.1.
What is a Binary search tree?
5.2.
What are the traversal techniques in BST?
5.3.
What are the primary operations in a binary tree?
5.4.
What is the parent and child node in BST?
5.5.
What's the difference between a Binary tree and a Binary search tree?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Find the second largest element in BST

## Introduction

A Binary Search Tree (BST) is a node-based tree data structure.

In BST the left and right subtree will also be a binary search tree. The right subtree of a node will contain nodes with values greater than the node’s value and the left subtree will contain nodes with values lesser than the node’s value.

## Finding the second largest element in BST

The second last element in inorder traversal is second largest element hence using inorder traversal, we can print the nodes in the binary search tree in ascending order. Then the nodes could be stored in an array, and upon returning the second to last element in the array, we would have the second largest element. Instead, we can traverse in reverse in order through the Binary Search Tree and count the nodes visited, we could print the node once the count becomes 2.

Let us take the following example:

The orange nodes are not visited yet. Lets traverse the nodes using inorder traversal.

• The root node is 50. We will move to the left subtree which is 40.

• It has subtree 35, so we traverse down to the left subtree of 35 which is 25. Here, 25 has no subtree, so we print 25 and move towards its parent node 35.
• Print 35 and move to its right subtree 38 and print it.

• Move to the root node of 35 that is 40. Since the left subtree of 40 is visited, we can print 40 and the right child which is 45.

• Next, we will move to the root node of 40 which is 50 and print it.
• Now let's traverse the right subtree of 50 that is 60. 60 has a subtree, so we will first traverse the left subtree 55.

• Node 55 has no children, so print 55 and move to its root node 60.

• Print 60 and traverse to the right subtree of 60, 70.

• Print the left subtree, which is 65
• We will print the root 70 and right substring 80

The final output after the completion of inorder traversal is

25, 35, 38, 40, 45, 50, 55, 60, 65, 70, 80

We will follow the same steps but in reverse order for reverse inorder traversal.

## Algorithm

Following is the Algorithm to find the second largest element in BST:

• Implement a Binary search tree.

• Insert the values of the node into BST.

• Traverse the nodes using the reverse inorder traversal method

• Keep a count of the number of nodes being visited

• Print the node once the count becomes 2.

Time complexity:

O(h) where h is the height of the Binary search tree.

Space Complexity:

O(n) for where n is the total number of nodes in the Binary search tree.

## Implementation

Following is the Implementation to find the second largest element in BST:

### C++

``````#include<bits/stdc++.h>
using namespace std;

struct Node
{
int key;
Node *left, *right;
};

// For creating a new BST node
Node *newNode(int item)
{
Node *tmp = new Node;
tmp->key = item;
tmp->left = tmp->right = NULL;
return tmp;
}

// To find the second largest element in a tree.
void secondLargestUtil(Node *root, int &c)
{

if (root == NULL || c >= 2)
return;

secondLargestUtil(root->right, c);
c++;

if (c == 2)
{
cout << "The second largest element is "
<< root->key << endl;
return;
}

secondLargestUtil(root->left, c);
}

// To find the second largest element
void secondLargest(Node *root)
{
int c = 0;
secondLargestUtil(root, c);
}

// To insert a new node in BST
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left  = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}

// Main functions
int main()
{
/* Let us create the following BST
50
/       \
40       60
/  \        /     \
35   45  55   70 */
Node *root = NULL;
root = insert(root, 50);
insert(root, 40);
insert(root, 35);
insert(root, 45);
insert(root, 60);
insert(root, 55);
insert(root, 70);
secondLargest(root);
return 0;
}``````

Output:

``The second largest element is 60``

### PYTHON

``````# element in BST
class Node:

# Constructor for creating a new BST node
def __init__(self, data):
self.key = data
self.left = None
self.right = None

# To find the second largest element in a given tree.
def secondLargestUtil(root, c):
if root == None or c[0] >= 2:
return

secondLargestUtil(root.right, c)
c[0] += 1
if c[0] == 2:
print("The second largest element is", root.key)
return

secondLargestUtil(root.left, c)

# To find the second largest element
def secondLargest(root):
c = [0]
secondLargestUtil(root, c)

def insert(node, key):
if node == None:
return Node(key)

if key < node.key:
node.left = insert(node.left, key)
elif key > node.key:
node.right = insert(node.right, key)
return node

# Main Code
if __name__ == '__main__':

# Let us create the following BST
#         50
#     /        \
#     40     60
#    /   \     /    \
# 35 45   55 70
root = None
root = insert(root, 50)
insert(root, 40)
insert(root, 35)
insert(root, 45)
insert(root, 60)
insert(root, 55)
insert(root, 70)
secondLargest(root) ``````

Output:

``The second largest element is 60``

### JAVA

``````// Java code to find the second largest element in BST

// For creating a new node
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}

class BinarySearchTree {

Node root;
BinarySearchTree()
{
root = null;
}

// For inserting new nodes
public void insert(int data)
{
this.root = this.insertRec(this.root, data);
}

Node insertRec(Node node, int data)
{
if (node == null) {
this.root = new Node(data);
return this.root;
}

if (data < node.data) {
node.left = this.insertRec(node.left, data);
} else {
node.right = this.insertRec(node.right, data);
}
return node;
}

public class count {
int c = 0;
}

// To find the second largest element
void secondLargestUtil(Node node, count C)
{
if (node == null || C.c >= 2)
return;

this.secondLargestUtil(node.right, C);
C.c++;

if (C.c == 2) {
System.out.print("The second largest element is "+
node.data);
return;
}
this.secondLargestUtil(node.left, C);
}

// To find the second largest element
void secondLargest(Node node)
{
count C = new count();
this.secondLargestUtil(this.root, C);
}

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

/* Let us create the following BST
50
/        \
40        60
/   \       /     \
35   45  55   70 */

tree.insert(50);
tree.insert(40);
tree.insert(35);
tree.insert(45);
tree.insert(60);
tree.insert(55);
tree.insert(70);

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

Output:

``The second largest element is 60``

### What is a Binary search tree?

A Binary Search Tree (BST) is a node-based tree data structure. In BST, the left and right subtree will also be a binary search tree. The right subtree of a node will contain nodes with values greater than the node's value, and the left subtree will have nodes with values lesser than the node's value.

### What are the traversal techniques in BST?

There are three traversal techniques: Inorder traversal, Preorder traversal, and Postorder traversal.

### What are the primary operations in a binary tree?

The main operations in binary tree are insert, search and delete.

### What is the parent and child node in BST?

The predecessor of any node is called the parent node. The node that is the immediate successor of a node is called the child node. Nodes with no children are called leaves or external nodes.

### What's the difference between a Binary tree and a Binary search tree?

In BST, the values of the left subtree of a node should be lesser than the parent node, and the right subtree values should be greater. But when it comes to a binary tree, there is no such requirement.

## Conclusion

We have learned how to find the second largest element in BST using reverse in-order traversal. To get a better understanding, look into How to get better at DSA for Beginners

Check out this problem - Reverse Nodes In K Group

Refer to our Test Seriesproblems listsproblems, participate in contests, and take a look at our courses that will help you become proficient in DSA in PythonC++Java, and Competitive programmingThese Interview experiences will give you a heads-up on what you must prepare for!

Look into our Library to explore more courses!

Thank you!

Live masterclass