Second largest element in Binary Search Tree

By | April 3, 2016

Second largest element in Binary Search Tree (BST).

Problem statement to find the second largest element in a Binary Search Tree (BST)

Given a binary search tree, determine its second largest element. In inorder traversal, the second last element is the second largest while in reverse inorder traversal, the second element is second largest element.

Example:

INPUT:
              10
           /     \
           5      15
         /  \    /  \
        1   8   12   20
OUTPUT:The second largest element is 15.

Determine the Second largest element in a Binary Search Tree Solution:

  1. Start reverse inorder traversal.
  2. For reverse inorder traversal, traverse the right subtree first, followed by the left subtree.
  3. Initialise a counter variable as count=0.
  4. Continue till count = 2 to stop at the second element(In reverse inorder traversal, second element is second largest element).
  5. Print this element.

Solution code in C++ for finding the second largest element in BST:

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

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and 
initialise new nodes*/
node *newNode(int key)
{
   node *temp = new node;
   temp->left = NULL;
   temp->right = NULL;
   temp->data = key;
   return temp;
}

/*This function is used to insert new nodes*/
node * Insert (node *root, int data)
{
   if(!root)
      return newNode(data);
      
   else if(data<root->data)
      root->left = Insert(root->left, data);
      
   else
      root->right = Insert(root->right,data);
      
   return root;
}

/*Function to determine the second largest element*/
void SecondLargest(node *root, int &count)
{
   /*Second condition helps to avoid recursive calls*/
   if(!root || count>=2)
      return;
      
   /*Follow reverse inorder traversal*/
   /*Recur for right subtree*/
   SecondLargest(root->right, count);
   
   count++;
   
   if(count==2)
   {
      cout<<"Second largest element is "<<root->data<<"\n";
      return;
   }
   
   /*Recur for left subtree*/
   SecondLargest(root->left, count);
}

/*Driver program to test above functions*/
int main() {
    /* The following insertions create this
    	Binary Search Tree
              80
           /     \
          60      110
         /  \    /  \
       35   40  85   130 */
       
    node *root = NULL;
    root = Insert(root, 80);
    Insert(root, 110);
    Insert(root, 85);
    Insert(root, 130);
    Insert(root, 60);
    Insert(root, 40);
    Insert(root, 35);
    
    int count = 0;
    SecondLargest(root, count);
    
   return 0;
}

Output:

Second largest element is 110.

Time Complexity: O(h)
where h is the height of the tree.