How to find Second largest element in BST ?

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 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.


    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 
        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.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) 
        // Follow reverse inorder traversal so that the 
        // largest element is visited first 
        this.secondLargestUtil(node.right, C);  
         // Increment count of visited nodes 
        // If c becomes k now, then this is the 2nd largest 
        if (C.c == 2) { 
            System.out.print("2nd largest element is "+ 
         // 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 
           /     \ 
          30      70 
         /  \    /  \ 
       20   40  60   80 */


2nd largest element is 70

Time Complexity

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

Related Searches to How to find Second largest element in BST ?