How to find Second largest element in BST ?

  • In an N-ary tree, the second largest value in the given tree to find and return the node. Return NULL if no node with required value is present.
  • For example, in the given tree
Second largest element in a BST

Second largest node is 20.

  • A simple solution is to traverse the array twice. In the first traversal the maximum value node to be find.
  • In the second traversal find the greatest element node less than the element obtained in first traversal.
  • This solution O(n) is the time complexity.
  • To find the second largest element in a single traversal to be efficient solution.

Algorithm

Initialize two nodes first and second to NULL as,
first = second = NULL

Start traversing the tree,
If the current node data say root->key is greater
than first->key then update first and second as,
second = first
first = root
If the current node data is in between first and
second, then update second to store the value
of current node as
second = root

Return the node stored in second.

Sample Code in Java

// Java code to find second largest element in BST 

// A binary tree node
class Node {

int data;
Node left, right;

Node(int d)
{
data = d;
left = right = null;
}
}

class BinarySearchTree {

// Root of BST
Node root;

// Constructor
BinarySearchTree()
{
root = null;
}

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

/* A utility function to insert a new node with given
key in BST */
Node insertRec(Node node, int data)
{
/* If the tree is empty, return a new node */
if (node == null) {
this.root = new Node(data);
return this.root;
}

/* Otherwise, recur down the tree */
if (data < node.data) {
node.left = this.insertRec(node.left, data);
} else {
node.right = this.insertRec(node.right, data);
}
return node;
}

// class that stores the value of count
public class count {
int c = 0;
}

// Function to find 2nd largest element
void secondLargestUtil(Node node, count C)
{
// Base cases, the second condition is important to
// avoid unnecessary recursive calls
if (node == null || C.c >= 2)
return;

// Follow reverse inorder traversal so that the
// largest element is visited first
this.secondLargestUtil(node.right, C);

// Increment count of visited nodes
C.c++;

// If c becomes k now, then this is the 2nd largest
if (C.c == 2) {
System.out.print("2nd largest element is "+
node.data);
return;
}

// Recur for left subtree
this.secondLargestUtil(node.left, C);
}

// Function to find 2nd largest element
void secondLargest(Node node)
{
// object of class count
count C = new count();
this.secondLargestUtil(this.root, C);
}

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

/* Let us create following BST
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

2nd largest element is 70

Time Complexity

  • Time Complexity: The above solution is O(h) where h is height of BST.

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,